Relevant bibliographies by topics / K-graph system

Academic literature on the topic 'K-graph system'

Author: Grafiati
Published: 25 May 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Contents

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'K-graph system.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "K-graph system"

1

Il’ev, A. V., and V. P. Il’ev. "ALGORITHMS FOR SOLVING SYSTEMS OF EQUATIONS OVER VARIOUS CLASSES OF FINITE GRAPHS." Prikladnaya Diskretnaya Matematika, no. 53 (2021): 89–102. http://dx.doi.org/10.17223/20710410/53/6.

Full text
Abstract:
The aim of the paper is to study and to solve finite systems of equations over finite undirected graphs. Equations over graphs are atomic formulas of the language L consisting of the set of constants (graph vertices), the binary vertex adjacency predicate and the equality predicate. It is proved that the problem of checking compatibility of a system of equations S with k variables over an arbitrary simple n-vertex graph Γ is N P-complete. The computational complexity of the procedure for checking compatibility of a system of equations S over a simple graph Γ and the procedure for finding a general solution of this system is calculated. The computational complexity of the algorithm for solving a system of equations S with k variables over an arbitrary simple n-vertex graph Γ involving these procedures is O(k 2n k/2+1(k + n) 2 ) for n > 3. Polynomially solvable cases are distinguished: systems of equations over trees, forests, bipartite and complete bipartite graphs. Polynomial time algorithms for solving these systems with running time O(k 2n(k + n) 2 ) are proposed.
APA, Harvard, Vancouver, ISO, and other styles
2

Asif, Muhammad, Hamad Almohamedh, Muhammad Hussain, Khalid M. Alhamed, Abdulrazaq A. Almutairi, and Sultan Almotairi. "An Approach to the Geometric-Arithmetic Index for Graphs under Transformations’ Fact over Pendent Paths." Complexity 2021 (June 24, 2021): 1–13. http://dx.doi.org/10.1155/2021/3745862.

Full text
Abstract:
Graph theory is a dynamic tool for designing and modeling of an interconnection system by a graph. The vertices of such graph are processor nodes and edges are the connections between these processors nodes. The topology of a system decides its best use. Geometric-arithmetic index is one of the most studied graph invariant to characterize the topological aspects of underlying interconnection networks or graphs. Transformation over graph is also an important tool to define new network of their own choice in computer science. In this work, we discuss transformed family of graphs. Let Γ n k , l be the connected graph comprises by k number of pendent path attached with fully connected vertices of the n-vertex connected graph Γ . Let A α Γ n k , l and A α β Γ n k , l be the transformed graphs under the fact of transformations A α and A α β , 0 ≤ α ≤ l , 0 ≤ β ≤ k − 1 , respectively. In this work, we obtained new inequalities for the graph family Γ n k , l and transformed graphs A α Γ n k , l and A α β Γ n k , l which involve GA Γ . The presence of GA Γ makes the inequalities more general than all those which were previously defined for the GA index. Furthermore, we characterize extremal graphs which make the inequalities tight.
APA, Harvard, Vancouver, ISO, and other styles
3

Ustimenko, Vasyl O., and Oleksandr S. Pustovit. "On security of GIS systems with N-tier architecture and family of graph based ciphers." Environmental safety and natural resources 47, no. 3 (September 29, 2023): 113–32. http://dx.doi.org/10.32347/2411-4049.2023.3.113-132.

Full text
Abstract:
Discovery of q-regular tree description in terms of an infinite system of quadratic equations over finite field Fq had an impact on Computer Science, theory of graph based cryptographic algorithms in particular. It stimulates the development of new graph based stream ciphers. It turns out that such encryption instruments can be efficiently used in GIS protection systems which use N-Tier Architecture. We observe known encryption algorithms based on the approximations of regular tree, their modifications defined over arithmetical rings and implementations of these ciphers. Additionally new more secure graph based ciphers suitable for GIS protection will be presented.Algorithms are constructed using vertices of bipartite regular graphs D(n,K) defined by a finite commutative ring K with a unit and a non-trivial multiplicative group K*. The partition of such graphs are n-dimensional affine spaces over the ring K. A walk of even length determines the transformation of the transition from the initial to the last vertex from one of the partitions of the graph. Therefore, the affine space Kn can be considered as a space of plaintexts, and walking on the graph is a password that defines the encryption transformation.With certain restrictions on the password the effect when different passwords with K*)2s, s <[(n+5)/2]/2 correspond to different ciphertexts of the selected plaintext with Kn can be achieved.In 2005, such an algorithm in the case of the finite field F127 was implemented for the GIS protection. Since then, the properties of encryption algorithms using D(n, K) graphs (execution speed, mixing properties, degree and density of the polynomial encryption transform) have been thoroughly investigated.The complexity of linearization attacks was evaluated and modifications of these algorithms with the resistance to linearization attacks were found. It turned out that together with D(n, K) graphs, other algebraic graphs with similar properties, such as A(n, K) graphs, can be effectively used.The article considers several solutions to the problem of protecting the geological information system from possible cyberattacks using stream ciphers based on graphs. They have significant advantages compared to the implemented earlier systems.
APA, Harvard, Vancouver, ISO, and other styles
4

RANAWAKE, U. A., P. M. LENDERS, and S. M. GOODNICK. "ON LOWER BOUNDS FOR THE COMMUNICATION VOLUME IN DISTRIBUTED SYSTEMS." Parallel Processing Letters 01, no. 02 (December 1991): 125–33. http://dx.doi.org/10.1142/s0129626491000070.

Full text
Abstract:
In this paper we derive a lower bound for the total communication volume when mapping arbitrary task graphs onto a distributed processor system. For a K processor system this lower bound can be computed with only the K (possibly) largest eigen values of the adjacency matrix of the task graph and the eigen values of the adjacency matrix of the processor graph. We also derive the eigen values of the adjacency matrix of the processor graph for a hypercube multiprocessor and illustrate the concept with a simple example for the two processor case.
APA, Harvard, Vancouver, ISO, and other styles
5

Lobov, Alexander A., and Mikhail B. Abrosimov. "About uniqueness of the minimal 1-edge extension of hypercube Q4." Prikladnaya Diskretnaya Matematika, no. 58 (2023): 84–93. http://dx.doi.org/10.17223/20710410/58/8.

Full text
Abstract:
One of the important properties of reliable computing systems is their fault tolerance. To study fault tolerance, you can use the apparatus of graph theory. Minimal edge extensions of a graph are considered, which are a model for studying the failure of links in a computing system. A graph G* = (V*,α*) with n vertices is called a minimal k-edge extension of an n-vertex graph G = (V, α) if the graph G is embedded in every graph obtained from G* by deleting any of its k edges and has the minimum possible number of edges. The hypercube Qn is a regular 2n-vertex graph of order n, which is the Cartesian product of n complete 2-vertex graphs K2. The hypercube is a common topology for building computing systems. Previously, a family of graphs Q*n was described, whose representatives for n>1 are minimal edge 1-extensions of the corresponding hypercubes. In this paper, we obtain an analytical proof of the uniqueness of minimal edge 1-extensions of hypercubes for n≤4 and establish a general property of an arbitrary minimal edge 1-extension of a hypercube Qn for n>2: it does not contain edges connecting vertices, the distance between which in the hypercube is equal to 2.
APA, Harvard, Vancouver, ISO, and other styles
6

Chen, Haiyan, and Fuji Zhang. "Spectral Dynamics of Graph Sequences Generated by Subdivision and Triangle Extension." Electronic Journal of Linear Algebra 32 (February 6, 2017): 454–63. http://dx.doi.org/10.13001/1081-3810.3583.

Full text
Abstract:
For a graph G and a unary graph operation X, there is a graph sequence \G_k generated by G_0=G and G_{k+1}=X(G_k). Let Sp({G_k}) denote the set of normalized Laplacian eigenvalues of G_k. The set of limit points of \bigcup_{k=0}^\infty Sp(G_k)$, $\liminf_{k\rightarrow\infty}Sp(G_k) and $\limsup_{k\rightarrow \infty}Sp(G_k)$ are considered in this paper for graph sequences generated by two operations: subdivision and triangle extension. It is obtained that the spectral dynamic of graph sequence generated by subdivision is determined by a quadratic function, which is closely related to the the well-known logistic map; while that generated by triangle extension is determined by a linear function. By using the knowledge of dynamic system, the spectral dynamics of graph sequences generated by these two operations are characterized. For example, it is found that, for any initial non-trivial graph $G$, chaos takes place in the spectral dynamics of iterated subdivision graphs, and the set of limit points is the entire closed interval [0,2].
APA, Harvard, Vancouver, ISO, and other styles
7

Razumovsky, P. V., and M. B. Abrosimov. "THE MINIMAL VERTEX EXTENSIONS FOR COLORED COMPLETE GRAPHS." Bulletin of the South Ural State University series "Mathematics. Mechanics. Physics" 13, no. 4 (2021): 77–89. http://dx.doi.org/10.14529/mmph210409.

Full text
Abstract:
The article proposes the results of the search for minimal vertex extensions of undirected colored complete graphs. The research topic is related to the modelling of full fault tolerant technical systems with a different type of their objects in the terminology of graph theory. Let a technical system be Σ, then there is a graph G(Σ), which vertices reflects system’s objects and edges reflects connections between these objects. Type of each object reflected in a mapping of some color from F = {1,2…,i} to the corresponding vertex. System’s Σ vertex extension is a graph G(Σ) which contains additional vertices. System reflected by graph G(Σ) can work even if there are k faults of its objects. Complete graph is a graph where each two vertices have an edge between them. Complete graphs have no edge extensions because there is no way to add additional edge to the graph with a maximum number of edges. In other words, the system reflected by some complete graph cannot be able to resist connection faults. Therefore the article research is focused on vertex extensions only. There is a description of vertex extensions existence condition for those colored complete graphs. This paper considers generating schemes for such minimal vertex extensions along with formulas, which allows to calculate number of additional edges to have an ability to construct minimal vertex extension.
APA, Harvard, Vancouver, ISO, and other styles
8

Aslam, Adnan, Safyan Ahmad, Muhammad Ahsan Binyamin, and Wei Gao. "Calculating topological indices of certain OTIS interconnection networks." Open Chemistry 17, no. 1 (April 10, 2019): 220–28. http://dx.doi.org/10.1515/chem-2019-0029.

Full text
Abstract:
AbstractRecently, increasing attention has been paid to The Optical Transpose Interconnection System (OTIS) network because of its prospective applications in architectures for parallel as well as distributed systems [27, 28]. Different interconnection networks in the context of topological indices are researched recently in [25, 26]. This article includes the computions of the general Randi´c, first and second Zagreb, general sum connectivity, first and second multiple zagreb, hyper zagreb, ABC and GA indices for OTIS (swapped and biswapped) networks by taking path and k-regular graph on n vertices as a base graphs. In addition, some delicated formulas are also obtained for the ABC4 and GA5 indices for the OTIS biswapped networks by considering basis graph as a path and k-regular graph of order n.
APA, Harvard, Vancouver, ISO, and other styles
9

Shirdel, G. H., M. Ghanbari, and M. Ramezani. "Generalized 3-Rainbow Domination in Graphs and Honeycomb System (HC(n))." Utilitas Mathematica 119, no. 1 (March 31, 2024): 3–7. http://dx.doi.org/10.61091/um119-01.

Full text
Abstract:
In this paper, we introduce the concept of the generalized 3 -rainbow dominating function of a graph G . This function assigns an arbitrary subset of three colors to each vertex of the graph with the condition that every vertex (including its neighbors) must have access to all three colors within its closed neighborhood. The minimum sum of assigned colors over all vertices of G is defined as the g 3 -rainbow domination number, denoted by γ g 3 r . We present a linear-time algorithm to determine a minimum generalized 3-rainbow dominating set for several graph classes: trees, paths ( P n ) , cycles ( C n ) , stars ( K 1 , n ) , generalized Petersen graphs ( G P ( n , 2 ) , GP ( n , 3 ) ) , and honeycomb networks ( H C ( n ) ) .
APA, Harvard, Vancouver, ISO, and other styles
10

Pavlopoulou, Niki. "Dynamic Diverse Summarisation in Heterogeneous Graph Streams: a Comparison between Thesaurus/Ontology-based and Embeddings-based Approaches." International Journal of Graph Computing 1, no. 1 (March 1, 2020): 70–94. http://dx.doi.org/10.35708/gc1868-126724.

Full text
Abstract:
Nowadays, there is a lot of attention drawn in smart environments, like Smart Cities and Internet of Things. These environments generate data streams that could be represented as graphs, which can be analysed in real-time to satisfy user or application needs. The challenges involved in these environments, ranging from the dynamism, heterogeneity, continuity, and high-volume of these real-world graph streams create new requirements for graph processing algorithms. We propose a dynamic graph stream summarisation system with the use of embeddings that provides expressive graphs while ensuring high usability and limited resource usage. In this paper, we examine the performance comparison between our embeddings-based approach and an existing thesaurus/ontology-based approach (FACES) that we adapted in a dynamic environment with the use of windows and data fusion. Both approaches use conceptual clustering and top-k scoring that can result in expressive, dynamic graph summaries with limited resources. Evaluations show that sending top-k fused diverse summaries, results in 34% to 92% reduction of forwarded messages and redundancy-awareness with an F-score ranging from 0.80 to 0.95 depending on the k compared to sending all the available information without top-k scoring. Also, the summaries' quality follows the agreement of ideal summaries determined by human judges. The summarisation approaches come with the expense of reduced system performance. The thesaurus/ontology-based approach proved 6 times more latency-heavy and 3 times more memory-heavy compared to the most expensive embeddings-based approach while having lower throughput but provided slightly better quality summaries.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "K-graph system"

1

Wang, Bin. "Rainbow structures in properly edge-colored graphs and hypergraph systems." Electronic Thesis or Diss., université Paris-Saclay, 2024. http://www.theses.fr/2024UPASG016.

Full text
Abstract:
La combinatoire extrémale est l'une des branches les plus vigoureuses des mathématiques combinatoires au cours des dernières décennies, et elle a été largement utilisée en informatique, en conception de réseaux et en conception de codage. Elle se concentre sur la détermination de la taille maximale ou minimale possible de certaines structures combinatoires, sous certaines conditions ou contraintes. Les ensembles hôtes peuvent être des graphes, des digraphes, des graphes aléatoires, des hypergraphes, des entiers, des nombres premiers, des ensembles, des graphes avec arêtes colorées, etc. Les structures locales peuvent être des appariements, des cliques, des cycles, des arbres, des sous-graphes couvrants (facteurs F, cycles Hamiltoniens), des familles d'intersection, des progressions arithmétiques, des solutions pour certaines équations (par exemple, x+y=z), des sous-graphes arc-en-ciel, etc. En particulier, la théorie des graphes extrémaux est une branche importante de la combinatoire extrémale, qui traite principalement de la manière dont les propriétés générales d'un graphe contrôlent la structure locale du graphe. Nous étudions l'existence d'un cycle Hamiltonien rainbow dans les systèmes de k-graphes, l'existence d'un appariement parfait rainbow dans les systèmes de k-graphes et l'existence d'un cycle long arc-en-ciel dans des graphes correctement colorés par les arêtes
Extremal Combinatorics is one of the most vigorous branch of Combinatorial Mathematics in recent decades and it has been widely used in Computer Science, Network Design and Coding Design. It focuses on determining the maximum or minimum possible size of certain combinatorial structures, subject to certain conditions or constraints. The host sets could be graphs, digraphs, random graphs, hypergraphs, integers, primes, sets, edge-colored graphs and so on. The local structures could be matchings, cliques, cycles, trees, spanning subgraphs (F-factors, Hamilton cycles), intersecting families, arithmetic progressions, solutions for some equations (e.g. x₊y₌z), rainbow subgraphs and so on. In particular, Extremal Graph Theory is a significant branch of Extremal Combinatorics, which primarily explores how the overall properties of a graph influence its local structures. We study the existence of a rainbow Hamilton cycle in k-graph systems, the existence of rainbow perfect matching in k-graph systems, and the existence of long rainbow cycle in properly edge-colored graphs
APA, Harvard, Vancouver, ISO, and other styles
2

Dyck, Johannes [Verfasser], Holger [Akademischer Betreuer] Giese, Holger [Gutachter] Giese, Arend [Gutachter] Rensink, and Heike [Gutachter] Wehrheim. "Verification of graph transformation systems with k-inductive invariants / Johannes Dyck ; Gutachter: Holger Giese, Arend Rensink, Heike Wehrheim ; Betreuer: Holger Giese." Potsdam : Universität Potsdam, 2020. http://d-nb.info/121816980X/34.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Li, Xiaohu. "Security Analysis on Network Systems Based on Some Stochastic Models." ScholarWorks@UNO, 2014. http://scholarworks.uno.edu/td/1931.

Full text
Abstract:
Due to great effort from mathematicians, physicists and computer scientists, network science has attained rapid development during the past decades. However, because of the complexity, most researches in this area are conducted only based upon experiments and simulations, it is critical to do research based on theoretical results so as to gain more insight on how the structure of a network affects the security. This dissertation introduces some stochastic and statistical models on certain networks and uses a k-out-of-n tolerant structure to characterize both logically and physically the behavior of nodes. Based upon these models, we draw several illuminating results in the following two aspects, which are consistent with what computer scientists have observed in either practical situations or experimental studies. Suppose that the node in a P2P network loses the designed function or service when some of its neighbors are disconnected. By studying the isolation probability and the durable time of a single user, we prove that the network with the user's lifetime having more NWUE-ness is more resilient in the sense of having a smaller probability to be isolated by neighbors and longer time to be online without being interrupted. Meanwhile, some preservation properties are also studied for the durable time of a network. Additionally, in order to apply the model in practice, both graphical and nonparametric statistical methods are developed and are employed to a real data set. On the other hand, a stochastic model is introduced to investigate the security of network systems based on their vulnerability graph abstractions. A node loses its designed function when certain number of its neighbors are compromised in the sense of being taken over by the malicious codes or the hacker. The attack compromises some nodes, and the victimized nodes become accomplices. We derived an equation to solve the probability for a node to be compromised in a network. Since this equation has no explicit solution, we also established new lower and upper bounds for the probability. The two models proposed herewith generalize existing models in the literature, the corresponding theoretical results effectively improve those known results and hence carry an insight on designing a more secure system and enhancing the security of an existing system.
APA, Harvard, Vancouver, ISO, and other styles
4

Swailes, David. "Some topics in industrial mathematics arising from a multi-national company : gel electrophoresis graph matching algorithm; modelling H'+ and K'+ transport across cell membranes; and micellization and adsorption processes in micellar systems." Thesis, University of Strathclyde, 1990. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.339870.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Davison, Benjamin Kenneth. "Universal graph literacy: understanding how blind and low vision students can satisfy the common core standards with accessible auditory graphs." Diss., Georgia Institute of Technology, 2013. http://hdl.handle.net/1853/47621.

Full text
Abstract:
Auditory graphs and active point estimation provide an inexpensive, accessible alternative for low vision and blind K-12 students using number lines and coordinate graphs. In the first phase of this research program, a series of four psychophysics studies demonstrated an interactive auditory number line that enables blind, low vision, and sighted people to find small targets with a laptop, headphones, and a mouse or a keyboard. The Fitts' Law studies showed that, given appropriate auditory feedback, blind people can use a mouse. In addition, auditory feedback can generate target response patterns similar to when people use visual feedback. Phase two introduced SQUARE, a novel method for building accessible alternatives to existing education technologies. The standards-driven and teacher-directed approach generated 17 graphing standards for sixth grade mathematics, all of which emphasized point estimation. It also showed that how only few basic behavioral components are necessary for these graphing problems. The third phase evaluated active point estimation tools in terms of training, classroom situations, and a testing situation. This work shows that students can learn to graph in K-12 environments, regardless of their visual impairment. It also provides several technologies used for graphing, and methods to further develop education accessibility research.
APA, Harvard, Vancouver, ISO, and other styles
6

Морозов, Костянтин В’ячеславович. "Методи і засоби побудови моделей поведінки небазових відмовостійких багатопроцесорних систем." Doctoral thesis, Київ, 2021. https://ela.kpi.ua/handle/123456789/40485.

Full text
Abstract:
Дисертація присвячена проблемі побудови графо-логічних моделей (GL-моделей) небазових відмовостійких багатопроцесорних систем (ВБС) з метою розрахунку їх параметрів надійності шляхом проведення статистичних експериментів із вищезгаданими моделями. Запропоновано метод перетворення GL-моделей за рахунок модифікації виразу будь-якої реберної функції так званої МВР-моделі. Метод базуються на зміні як однієї, так і обох частин виразу реберної функції та дозволяє модифікувати модель так, що на деяких векторах стану системи вона, на відміну від оригінальної, починає показувати роботозданий і/або нероботоздатний стан. Проаналізовано межі впливу для загального випадку модифікації як однієї, так і кількох реберних функцій на зміну поведінки моделі. Вперше запропоновано аналітичний апарат, що дозволяє визначати вектор стану t-діагностованої ВБС на основі результатів взаємного тестування процесорів, згідно із моделлю Препарати-Метца-Чена (ПМЧ-модель), для довільної топології зв’язків між ними. Вперше запропоновано метод побудови GL-моделей так званих зважених систем, в яких кожний компонент має деяку вагу, що характеризує його вклад в роботоздатність системи в цілому, а також узагальнення методу побудови GL-моделей, що базується на використанні в якості реберних функцій багатозначної логіки та дозволяє використовувати їх для побудови моделей систем, для яких, як і їх компонентів характерні більше двох станів роботоздатності. Запропоновано метод побудови GL-моделей ієрархічних систем шляхом композиції декількох МВР-моделей, а також моделей систем, що складаються з кількох підсистем та мають ковзний резерв.
APA, Harvard, Vancouver, ISO, and other styles
7

Bodin, Bruno. "Analyse d'Applications Flot de Données pour la Compilation Multiprocesseur." Phd thesis, Université Pierre et Marie Curie - Paris VI, 2013. http://tel.archives-ouvertes.fr/tel-00922578.

Full text
Abstract:
Les systèmes embarqués sont des équipements électroniques et informatiques, soumis à de nombreuses contraintes et dont le fonctionnement doit être continu. Pour définir le comportement de ces systèmes, les modèles de programmation dataflows sont souvent utilisés. Ce choix de modèle est motivé d'une part, parce qu'ils permettent de décrire un comportement cyclique, nécessaire aux systèmes embarqués ; et d'autre part, parce que ces modèles s'apprêtent à des analyses qui peuvent fournir des garanties de fonctionnement et de performance essentielles. La société Kalray propose une architecture embarquée, le MPPA. Il est accompagné du langage de programmation ΣC. Ce langage permet alors de décrire des applications sous forme d'un modèle dataflow déjà très étudié, le modèle Cyclo-Static Dataflow Graph(CSDFG). Cependant, les CSDFG générés par ce langage sont souvent trop complexes pour permettre l'utilisation des techniques d'analyse existantes. L'objectif de cette thèse est de fournir des outils algorithmiques qui résolvent les différentes étapes d'analyse nécessaires à l'étude d'une application ΣC, mais dans un temps d'exécution raisonnable, et sur des instances de grande taille. Nous étudions trois problèmes d'analyse distincts : le test de vivacité, l'évaluation du débit maximal, et le dimensionnement mémoire. Pour chacun de ces problèmes, nous fournissons des méthodes algorithmiques rapides, et dont l'efficacité a été vérifiée expérimentalement. Les méthodes que nous proposons sont issues de résultats sur les ordonnancements périodiques ; elles fournissent des résultats approchés et sans aucune garantie de performance. Pour pallier cette faiblesse, nous proposons aussi de nouveaux outils d'analyse basés sur les ordonnancements K-périodiques. Ces ordonnancements généralisent nos travaux d'ordonnancement périodiques et nous permettrons dans un avenir proche de concevoir des méthodes d'analyse bien plus efficaces.
APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "K-graph system"

1

Banerjee, Tamajit, Rupak Majumdar, Kaushik Mallik, Anne-Kathrin Schmuck, and Sadegh Soudjani. "A Direct Symbolic Algorithm for Solving Stochastic Rabin Games." In Tools and Algorithms for the Construction and Analysis of Systems, 81–98. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-030-99527-0_5.

Full text
Abstract:
AbstractWe consider turn-based stochastic 2-player games on graphs with $$\omega $$ ω -regular winning conditions. We provide a direct symbolic algorithm for solving such games when the winning condition is formulated as a Rabin condition. For a stochastic Rabin game with k pairs over a game graph with n vertices, our algorithm runs in $$O(n^{k+2}k!)$$ O ( n k + 2 k ! ) symbolic steps, which improves the state of the art.We have implemented our symbolic algorithm, along with performance optimizations including parallellization and acceleration, in a BDD-based synthesis tool called . We demonstrate the superiority of compared to the state of the art on a set of synthetic benchmarks derived from the VLTS benchmark suite and on a control system benchmark from the literature. In our experiments, performed significantly faster with up to two orders of magnitude improvement in computation time.
APA, Harvard, Vancouver, ISO, and other styles
2

Sun, Wei, Laisheng Xiang, Xiyu Liu, and Dan Zhao. "An Improved K-medoids Clustering Algorithm Based on a Grid Cell Graph Realized by the P System." In Human Centered Computing, 365–74. Cham: Springer International Publishing, 2016. http://dx.doi.org/10.1007/978-3-319-31854-7_33.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Morais, Bruno, Miguel E. Coimbra, and Luís Veiga. "PK-Graph: Partitioned $$k^2$$-Trees to Enable Compact and Dynamic Graphs in Spark GraphX." In Cooperative Information Systems, 149–67. Cham: Springer International Publishing, 2022. http://dx.doi.org/10.1007/978-3-031-17834-4_9.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Larsen, Casper Abild, Simon Meldahl Schmidt, Jesper Steensgaard, Anna Blume Jakobsen, Jaco van de Pol, and Andreas Pavlogiannis. "A Truly Symbolic Linear-Time Algorithm for SCC Decomposition." In Tools and Algorithms for the Construction and Analysis of Systems, 353–71. Cham: Springer Nature Switzerland, 2023. http://dx.doi.org/10.1007/978-3-031-30820-8_22.

Full text
Abstract:
AbstractDecomposing a directed graph to its strongly connected components (SCCs) is a fundamental task in model checking. To deal with the state-space explosion problem, graphs are often represented symbolically using binary decision diagrams (BDDs), which have exponential compression capabilities. The theoretically-best symbolic algorithm for SCC decomposition is Gentilini et al’s $$\textsc {Skeleton}$$ S K E L E T O N algorithm, that uses O(n) symbolic steps on a graph of n nodes. However, $$\textsc {Skeleton}$$ S K E L E T O N uses $$\Theta (n)$$ Θ ( n ) symbolic objects, as opposed to (poly-)logarithmically many, which is the norm for symbolic algorithms, thereby relinquishing its symbolic nature. Here we present $$\textsc {Chain}$$ C H A I N , a new symbolic algorithm for SCC decomposition that also makes O(n) symbolic steps, but further uses logarithmic space, and is thus truly symbolic. We then extend $$\textsc {Chain}$$ C H A I N to $$\textsc {ColoredChain}$$ C O L O R E D C H A I N , an algorithm for SCC decomposition on edge-colored graphs, which arise naturally in model-checking a family of systems. Finally, we perform an experimental evaluation of $$\textsc {Chain}$$ C H A I N among other standard symbolic SCC algorithms in the literature. The results show that $$\textsc {Chain}$$ C H A I N is competitive on almost all benchmarks, and often faster, while it clearly outperforms all other algorithms on challenging inputs.
APA, Harvard, Vancouver, ISO, and other styles
5

Zou, Lei, Lei Chen, and Yansheng Lu. "Top-K Correlation Sub-graph Search in Graph Databases." In Database Systems for Advanced Applications, 168–85. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009. http://dx.doi.org/10.1007/978-3-642-00887-0_14.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Stokes, Klara. "Graph k-Anonymity through k-Means and as Modular Decomposition." In Secure IT Systems, 263–78. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. http://dx.doi.org/10.1007/978-3-642-41488-6_18.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Subercaseaux, Bernardo, and Marijn J. H. Heule. "The Packing Chromatic Number of the Infinite Square Grid is 15." In Tools and Algorithms for the Construction and Analysis of Systems, 389–406. Cham: Springer Nature Switzerland, 2023. http://dx.doi.org/10.1007/978-3-031-30823-9_20.

Full text
Abstract:
AbstractA packing k-coloring is a natural variation on the standard notion of graph k-coloring, where vertices are assigned numbers from $$\{1, \ldots , k\}$$ { 1 , … , k } , and any two vertices assigned a common color $$c \in \{1, \ldots , k\}$$ c ∈ { 1 , … , k } need to be at a distance greater than c (as opposed to 1, in standard graph colorings). Despite a sequence of incremental work, determining the packing chromatic number of the infinite square grid has remained an open problem since its introduction in 2002. We culminate the search by proving this number to be 15. We achieve this result by improving the best-known method for this problem by roughly two orders of magnitude. The most important technique to boost performance is a novel, surprisingly effective propositional encoding for packing colorings. Additionally, we developed an alternative symmetry breaking method. Since both new techniques are more complex than existing techniques for this problem, a verified approach is required to trust them. We include both techniques in a proof of unsatisfiability, reducing the trusted core to the correctness of the direct encoding.
APA, Harvard, Vancouver, ISO, and other styles
8

Nayak, Satya Prakash, and Anne-Kathrin Schmuck. "Most General Winning Secure Equilibria Synthesis in Graph Games." In Tools and Algorithms for the Construction and Analysis of Systems, 173–93. Cham: Springer Nature Switzerland, 2024. http://dx.doi.org/10.1007/978-3-031-57256-2_9.

Full text
Abstract:
AbstractThis paper considers the problem of co-synthesis in k-player games over a finite graph where each player has an individual $$\omega $$ ω -regular specification $$\phi _i$$ ϕ i . In this context, a secure equilibrium (SE) is a Nash equilibrium w.r.t. the lexicographically ordered objectives of each player to first satisfy their own specification, and second, to falsify other players’ specifications. A winning secure equilibrium (WSE) is an SE strategy profile $$(\pi _i)_{i\in [1;k]}$$ ( π i ) i ∈ [ 1 ; k ] that ensures the specification $$\phi :=\bigwedge _{i\in [1;k]}\phi _i$$ ϕ : = ⋀ i ∈ [ 1 ; k ] ϕ i if no player deviates from their strategy $$\pi _i$$ π i . Distributed implementations generated from a WSE make components act rationally by ensuring that a deviation from the WSE strategy profile is immediately punished by a retaliating strategy that makes the involved players lose.In this paper, we move from deviation punishment in WSE-based implementations to a distributed, assume-guarantee based realization of WSE. This shift is obtained by generalizing WSE from strategy profiles to specification profiles$$(\varphi _i)_{i\in [1;k]}$$ ( φ i ) i ∈ [ 1 ; k ] with $$\bigwedge _{i\in [1;k]}\varphi _i = \phi $$ ⋀ i ∈ [ 1 ; k ] φ i = ϕ , which we call most general winning secure equilibria (GWSE). Such GWSE have the property that each player can individually pick a strategy $$\pi _i$$ π i winning for $$\varphi _i$$ φ i (against all other players) and all resulting strategy profiles $$(\pi _i)_{i\in [1;k]}$$ ( π i ) i ∈ [ 1 ; k ] are guaranteed to be a WSE. The obtained flexibility in players’ strategy choices can be utilized for robustness and adaptability of local implementations.Concretely, our contribution is three-fold: (1) we formalize GWSE for k-player games over finite graphs, where each player has an $$\omega $$ ω -regular specification $$\phi _i$$ ϕ i ; (2) we devise an iterative semi-algorithm for GWSE synthesis in such games, and (3) obtain an exponential-time algorithm for GWSE synthesis with parity specifications $$\phi _i$$ ϕ i .
APA, Harvard, Vancouver, ISO, and other styles
9

Hausmann, Daniel, and Lutz Schröder. "Quasipolynomial Computation of Nested Fixpoints." In Tools and Algorithms for the Construction and Analysis of Systems, 38–56. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-72016-2_3.

Full text
Abstract:
AbstractIt is well-known that the winning region of a parity game with n nodes and k priorities can be computed as a k-nested fixpoint of a suitable function; straightforward computation of this nested fixpoint requires $$\mathcal {O}(n^{\frac{k}{2}})$$ O ( n k 2 ) iterations of the function. Calude et al.’s recent quasipolynomial-time parity game solving algorithm essentially shows how to compute the same fixpoint in only quasipolynomially many iterations by reducing parity games to quasipolynomially sized safety games. Universal graphs have been used to modularize this transformation of parity games to equivalent safety games that are obtained by combining the original game with a universal graph. We show that this approach naturally generalizes to the computation of solutions of systems of any fixpoint equations over finite lattices; hence, the solution of fixpoint equation systems can be computed by quasipolynomially many iterations of the equations. We present applications to modal fixpoint logics and games beyond relational semantics. For instance, the model checking problems for the energy $$\mu $$ μ -calculus, finite latticed $$\mu $$ μ -calculi, and the graded and the (two-valued) probabilistic $$\mu $$ μ -calculus – with numbers coded in binary – can be solved via nested fixpoints of functions that differ substantially from the function for parity games but still can be computed in quasipolynomial time; our result hence implies that model checking for these $$\mu $$ μ -calculi is in $$\textsc {QP}$$ QP . Moreover, we improve the exponent in known exponential bounds on satisfiability checking.
APA, Harvard, Vancouver, ISO, and other styles
10

Vasilyeva, Elena, Maik Thiele, Christof Bornhövd, and Wolfgang Lehner. "Top-k Differential Queries in Graph Databases." In Advances in Databases and Information Systems, 112–25. Cham: Springer International Publishing, 2014. http://dx.doi.org/10.1007/978-3-319-10933-6_9.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "K-graph system"

1

Kocan, F. "Reconfigurable randomized K-way graph partitioning." In Proceedings. Euromicro Symposium on Digital System Design. IEEE, 2003. http://dx.doi.org/10.1109/dsd.2003.1231947.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Chen, Penghe, Yu Lu, Vincent W. Zheng, Xiyang Chen, and Xiaoqing Li. "An automatic knowledge graph construction system for K-12 education." In L@S '18: Fifth (2018) ACM Conference on Learning @ Scale. New York, NY, USA: ACM, 2018. http://dx.doi.org/10.1145/3231644.3231698.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Wang, Yan, Amar Henni, Azade Fotouhi, and Leopold Mvondo Ze. "Leveraging K-hop based Graph for the Staffing Recommender System with Parametric Geolocation." In 2022 International Conference on Computational Science and Computational Intelligence (CSCI). IEEE, 2022. http://dx.doi.org/10.1109/csci58124.2022.00122.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Asgari, Zahra, and Maryam Sadat Mastoori. "Binomial Distribution based K-means for Graph Partitioning Approach in Partially Reconfigurable Computing system." In 2021 29th Iranian Conference on Electrical Engineering (ICEE). IEEE, 2021. http://dx.doi.org/10.1109/icee52715.2021.9544358.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Asgari, Zahra, and Maryam Sadat Mastoori. "Binomial Distribution based K-means for Graph Partitioning Approach in Partially Reconfigurable Computing system." In 2021 29th Iranian Conference on Electrical Engineering (ICEE). IEEE, 2021. http://dx.doi.org/10.1109/icee52715.2021.9544358.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Riveret, Regis, Son Tran, and Artur d'Avila Garcez. "Neuro-Symbolic Probabilistic Argumentation Machines." In 17th International Conference on Principles of Knowledge Representation and Reasoning {KR-2020}. California: International Joint Conferences on Artificial Intelligence Organization, 2020. http://dx.doi.org/10.24963/kr.2020/90.

Full text
Abstract:
Neural-symbolic systems combine the strengths of neural networks and symbolic formalisms. In this paper, we introduce a neural-symbolic system which combines restricted Boltzmann machines and probabilistic semi-abstract argumentation. We propose to train networks on argument labellings explaining the data, so that any sampled data outcome is associated with an argument labelling. Argument labellings are integrated as constraints within restricted Boltzmann machines, so that the neural networks are used to learn probabilistic dependencies amongst argument labels. Given a dataset and an argumentation graph as prior knowledge, for every example/case K in the dataset, we use a so-called K-maxconsistent labelling of the graph, and an explanation of case K refers to a K-maxconsistent labelling of the given argumentation graph. The abilities of the proposed system to predict correct labellings were evaluated and compared with standard machine learning techniques. Experiments revealed that such argumentation Boltzmann machines can outperform other classification models, especially in noisy settings.
APA, Harvard, Vancouver, ISO, and other styles
7

Stańczak, Jarosław, Jan Owsiński, Barbara Mażbic-Kulma, Aleksy Barski, and Krzysztof Sęp. "Evolutionary k-means Graph Clustering Method to Obtain the hub&spoke Structure for Warsaw Communication System." In 18th Conference on Computer Science and Intelligence Systems. PTI, 2023. http://dx.doi.org/10.15439/2023f9176.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

You, Li. "Multi-party quantum correlation and entanglement." In Workshop on Entanglement and Quantum Decoherence. Washington, D.C.: Optica Publishing Group, 2008. http://dx.doi.org/10.1364/weqd.2008.eas2.

Full text
Abstract:
A characterization of the complete correlation structure in an n-party system is proposed in terms of a series of (k, n) threshold classical secret sharing protocols (2 ≤ k ≤ n). The total correlation is shown to be the sum of independent correlations of 2-, 3-,…, n-parties. Our result unifies several earlier scattered works, and shines new light at the important topic of multi-party quantum entanglement. As an application, we explicitly construct the hierarchy of correlations in an n-qubit graph state.
APA, Harvard, Vancouver, ISO, and other styles
9

Seong, Bo-Ok, Jimin Ahn, Myeongjun Son, and Hyeongok Lee. "Three-degree graph and design of an optimal routing algorithm." In 13th International Conference on Applied Human Factors and Ergonomics (AHFE 2022). AHFE International, 2022. http://dx.doi.org/10.54941/ahfe1001466.

Full text
Abstract:
Learning, as well as the importance of a high-performance computer is significantly emerging. In parallel computing, we denote the concept of interconnection between the single memory and multiple processors as multi-processor. In a similar context, multi-computing signifies the connection of memory-loaded processors through the communication link. The relationship between the performance of multi-computing and the processor’s linkage structure is extremely proximate. Let the connection structure of the processor be an interconnection network. The interconnection network can be modeled through a classical graph consisting of node and edge. In this regard, a multi-computing processor is expressed as a node, communication link as an edge. When categorizing the suggested interconnection network through the criteria of the number of nodes, it can be classified as follows: Mesh class type consisted of the n×k nodes (Torus, Toroidal mesh, Diagonal mesh, Honeycomb mesh), Hypercube class type with 2^n nodes (Hypercube, Folded hypercube, Twisted cube, de Breijin), and Star graph class type (Star graph, Bubblesort star, Alternating group, Macro-star, Transposition) with n! nodes. The mesh type structure is a planar graph that is widely being utilized in the domains such as VLSI circuit design and base station installing (covering) problems in a mobile communication network. Mesh class types are comparatively easier to design and could potentially be implemented in algorithmic domains in a practical manner. Therefore, it is considered as a classical measure that is extensively preferred when designing a parallel computing network system. This study suggests the novel mesh structure De3 with the degree of three and designs an optimal routing algorithm as well as a parallel route algorithm (병렬경로알고리즘) based on the diameter analysis. The address of the node in the De3 graph is expressed with n-bit binary digits, and the edge is noted with the operator %. We built the interval function (구간 함수) that computes the locational property of the corresponding nodes to derive an optimal routing path from node u to node v among the De3 graph structure. We represent the optimal routing algorithm based on the interval function, calculating and validating the diameter of the De3 graph. Furthermore, we propose the algorithm that establishes the node disjoint parallel path which addresses a non-overlap path from node u to v. The outcome of this study proposes a novel interconnection network structure that is applicable in the routing algorithm optimization by limiting the communication links to three while the number of nodes These results implicate the viable operation among the high-performance edge computing system in a cost-efficient and effective manner.
APA, Harvard, Vancouver, ISO, and other styles
10

Zhao, Yue, Francesco Di Maio, Enrico Zio, Qin Zhang, and Chunling Dong. "Genetic Algorithm Optimization of a Dynamic Uncertain Causality Graph (DUCG) for Fault Diagnosis in Nuclear Power Plants." In 2016 24th International Conference on Nuclear Engineering. American Society of Mechanical Engineers, 2016. http://dx.doi.org/10.1115/icone24-60199.

Full text
Abstract:
Fault diagnostics is important for the safe operation of Nuclear Power Plants (NPPs). In recent years, data-driven approaches like neural networks, fuzzy and neuro-fuzzy approaches, support vector machine, K-nearest neighbors classifiers and inference methodologies, have been proposed and implemented to tackle the problem. Among these methodologies, Dynamic Uncertain Causality Graph (DUCG) has been proved effective in many practical cases. However, the causal graph construction behind the DUCG is complicated and, in many cases, redundant on the symptoms needed to correctly classify the fault. In this paper, we propose a method to simplify causal graph construction in an automatic way. The method consists in transforming the expert knowledge-based DCUG into a Fuzzy Decision Tree (FDT) by extracting from the DUCG a Fuzzy Rule Base (FRB). Genetic algorithm (GA) is, then, used for the optimization of the FDT, by performing a wrapper search around the FDT: the set of symptoms selected during the iterative search are taken as the best set of symptoms for the diagnosis of the faults that can occur in the system. The effectiveness of the approach is shown with respect to a DUCG model initially built to diagnose 23 faults originally using 262 symptoms of Unit-1 in the Ningde NPP of the China Guangdong Nuclear Power Corporation (CGNPC). Final results show that the FDT whose symptoms and diagnosis strategy has been optimized by GA, can drive the construction of DUCG and lower the computational burden without loss of accuracy in diagnosis.
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'K-graph system' for particular source types:
Journal articles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography