Journal articles on the topic 'Graph-based enumeration'
To see the other types of publications on this topic, follow the link: Graph-based enumeration.
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 journal articles for your research on the topic 'Graph-based enumeration.'
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.
Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.
1
Sanei-Mehri, Seyed-Vahid, Apurba Das, Hooman Hashemi, and Srikanta Tirthapura. "Mining Largest Maximal Quasi-Cliques." ACM Transactions on Knowledge Discovery from Data 15, no. 5 (June 26, 2021): 1–21. http://dx.doi.org/10.1145/3446637.
Full textAbstract:
Quasi-cliques are dense incomplete subgraphs of a graph that generalize the notion of cliques. Enumerating quasi-cliques from a graph is a robust way to detect densely connected structures with applications in bioinformatics and social network analysis. However, enumerating quasi-cliques in a graph is a challenging problem, even harder than the problem of enumerating cliques. We consider the enumeration of top- k degree-based quasi-cliques and make the following contributions: (1) we show that even the problem of detecting whether a given quasi-clique is maximal (i.e., not contained within another quasi-clique) is NP-hard. (2) We present a novel heuristic algorithm K ernel QC to enumerate the k largest quasi-cliques in a graph. Our method is based on identifying kernels of extremely dense subgraphs within a graph, followed by growing subgraphs around these kernels, to arrive at quasi-cliques with the required densities. (3) Experimental results show that our algorithm accurately enumerates quasi-cliques from a graph, is much faster than current state-of-the-art methods for quasi-clique enumeration (often more than three orders of magnitude faster), and can scale to larger graphs than current methods.
2
Simoni, Roberto, Andrea Piga Carboni, and Daniel Martins. "Enumeration of parallel manipulators." Robotica 27, no. 4 (July 2009): 589–97. http://dx.doi.org/10.1017/s0263574708004979.
Full textAbstract:
SUMMARYIn this paper, we present a new method of enumeration of parallel manipulators with one end-effector. The method consists of enumerating all the manipulators possible with one end-effector that a single kinematic chain can originate. A very useful simplification for kinematic chain, mechanism and manipulator enumeration is their representation through graphs. The method is based on group theory where abstract structures are used to capture the internal symmetry of a structure in the form of automorphisms of a group. The concept used is orbits of the group of automorphisms of a colored vertex graph. The theory and some examples are presented to illustrate the method.
3
shaik, Fathimabi, RBV Subramanyam, and DVLN Somayajulu. "Map-Reduce based Multiple Sub-Graph Enumeration Using Dominating-Set Graph Partition." International Journal of Information Engineering and Electronic Business 9, no. 2 (March 8, 2017): 36–44. http://dx.doi.org/10.5815/ijieeb.2017.02.05.
Full text
4
Trefftz, Christian, Hugh McGuire, Zachary Kurmas, and Jerry Scripps. "Exhaustive Community Enumeration in Parallel." Parallel Processing Letters 26, no. 02 (June 2016): 1650006. http://dx.doi.org/10.1142/s0129626416500067.
Full textAbstract:
An algorithm to evaluate/count all the possible communities of a graph is presented. An associated unrank function is described. An implementation of an existing algorithm to evaluate all the possible partitions of a graph, based on an unrank function, is presented as well. Performance results of the parallelizations of these algorithms obtained on a shared memory machine, a cluster of workstations and a Graphical Processing Unit (GPU) are included.
5
Ma, Ming Yue, and Xiang Yang Xu. "A Novel Algorithm for Enumeration of the Planetary Gear Train Based on Graph Theory." Advanced Materials Research 199-200 (February 2011): 392–99. http://dx.doi.org/10.4028/www.scientific.net/amr.199-200.392.
Full textAbstract:
As well known, graph theory is a powerful tool for mechanism design. The enumeration of planet gear trains can be converted the synthesis of graphs while a planetary gear train is converted to a graph. During the enumeration of graphs, the problem of isomorphism should be solved. This paper proposes a novel algorithm used to generate non-isomorphism graphs and thereby omits the part of isomorphism detection. The vertex characteristic is firstly defined in this paper that is the core of the enumeration algorithm. This paper also gives an example of the application for the algorithm.
6
Wang, Shanshan, Chenglong Xiao, and Wanjun Liu. "Parallel Enumeration of Custom Instructions Based on Multidepth Graph Partitioning." IEEE Embedded Systems Letters 11, no. 1 (March 2019): 1–4. http://dx.doi.org/10.1109/les.2018.2812784.
Full text
7
Chen, Lu, Chengfei Liu, Rui Zhou, Jiajie Xu, and Jianxin Li. "Efficient maximal biclique enumeration for large sparse bipartite graphs." Proceedings of the VLDB Endowment 15, no. 8 (April 2022): 1559–71. http://dx.doi.org/10.14778/3529337.3529341.
Full textAbstract:
Maximal bicliques are effective to reveal meaningful information hidden in bipartite graphs. Maximal biclique enumeration (MBE) is challenging since the number of the maximal bicliques grows exponentially w.r.t. the number of vertices in a bipartite graph in the worst case. However, a large bipartite graph is usually very sparse, which is against the worst case and may lead to fast MBE algorithms. The uncharted opportunity is taking advantage of the sparsity to substantially improve the MBE efficiency for large sparse bipartite graphs. We observe that for a large sparse bipartite graph, a vertex u may converge to a few vertices in the same vertex set as u via its neighbours, which reveals that the enumeration scope for a vertex could be very small. Based on this observation, we propose novel concepts: unilateral coreness for individual vertices, unilateral order for each vertex set and unilateral convergence (ζ) for a large sparse bipartite graph, ζ could be a few thousand for a large sparse bipartite graph with hundreds of million edges. Using the unilateral order, every vertex with τ unilateral coreness only needs to check at most 2 τ combinations so that all maximal bicliques can be enumerated and τ is bounded by ζ, which leads to a novel MBE algorithm running in O * (2 ζ ). We then propose a batch-pivots technique to eliminate all enumerations resulting in non-maximal bicliques, which guarantees that every maximal biclique is reported in O (ζ e )-delay, where e is the number of edges. We devise novel data structures that allow storing subgraphs at omissible space for further speeding up MBE. Extensive experiments are conducted on synthetic and real large datasets to justify that our proposed algorithm is faster and more scalable than the existing algorithms.
8
KHAKABIMAMAGHANI, SAHAND, MASOOD MASJOODY, and LADISLAV STACHO. "Traversal with Enumeration of Geometric Graphs in Bounded Space." Journal of Interconnection Networks 19, no. 04 (December 2019): 1950008. http://dx.doi.org/10.1142/s0219265919500087.
Full textAbstract:
In this paper, we provide an algorithm for traversing geometric graphs which visits all vertices and reports every vertex and edge exactly once. To achieve this, we combine a given geometric graph G with the integer lattice, seen as a graph, in such a way that the resulting hypothetical graph can be traversed using a known algorithm which is based on face routing. To overcome the problem with hypothetical vertices and edges, we develop an algorithm for visiting any k-th neighborhood of a vertex in a graph straight-line drawn in the plane using O(k log k) memory. The memory needed to complete the traversal of a geometric graph then turns out to depend on the maximum graph distance among pairs of distinct vertices of G whose Euclidean distance is greater than one and less than [Formula: see text].
9
Yang, Yu, An Wang, Hua Wang, Wei-Ting Zhao, and Dao-Qiang Sun. "On Subtrees of Fan Graphs, Wheel Graphs, and “Partitions” of Wheel Graphs under Dynamic Evolution." Mathematics 7, no. 5 (May 24, 2019): 472. http://dx.doi.org/10.3390/math7050472.
Full textAbstract:
The number of subtrees, or simply the subtree number, is one of the most studied counting-based graph invariants that has applications in many interdisciplinary fields such as phylogenetic reconstruction. Motivated from the study of graph surgeries on evolutionary dynamics, we consider the subtree problems of fan graphs, wheel graphs, and the class of graphs obtained from “partitioning” wheel graphs under dynamic evolution. The enumeration of these subtree numbers is done through the so-called subtree generation functions of graphs. With the enumerative result, we briefly explore the extremal problems in the corresponding class of graphs. Some interesting observations on the behavior of the subtree number are also presented.
10
Kruse, Sebastian, Zoi Kaoudi, Bertty Contreras-Rojas, Sanjay Chawla, Felix Naumann, and Jorge-Arnulfo Quiané-Ruiz. "RHEEMix in the data jungle: a cost-based optimizer for cross-platform systems." VLDB Journal 29, no. 6 (May 18, 2020): 1287–310. http://dx.doi.org/10.1007/s00778-020-00612-x.
Full textAbstract:
AbstractData analytics are moving beyond the limits of a single platform. In this paper, we present the cost-based optimizer of Rheem, an open-source cross-platform system that copes with these new requirements. The optimizer allocates the subtasks of data analytic tasks to the most suitable platforms. Our main contributions are: (i) a mechanism based on graph transformations to explore alternative execution strategies; (ii) a novel graph-based approach to determine efficient data movement plans among subtasks and platforms; and (iii) an efficient plan enumeration algorithm, based on a novel enumeration algebra. We extensively evaluate our optimizer under diverse real tasks. We show that our optimizer can perform tasks more than one order of magnitude faster when using multiple platforms than when using a single platform.
11
Simoni, R., A. P. Carboni, and D. Martins. "Enumeration of kinematic chains and mechanisms." Proceedings of the Institution of Mechanical Engineers, Part C: Journal of Mechanical Engineering Science 223, no. 4 (December 1, 2008): 1017–24. http://dx.doi.org/10.1243/09544062jmes1071.
Full textAbstract:
A problem still unsolved in kinematics is the enumeration of a complete list of kinematic chains and mechanisms without isomorphisms and without degenerate chains that operate in any screw system. In this paper, a method for the enumeration of kinematic chains without isomorphisms and degenerate chains for all screw systems and a new method of enumeration of kinematic chain inversions (i.e. mechanisms) based on group theory techniques are presented. New concepts of the group theory are introduced and a new method of enumeration of inversions is presented. Kinematic inversions are related to the symmetries of the chain which can be identified analysing the corresponding graph. The symmetry of a graph can be identified for the group of automorphisms of the graph and its orbits provides sets of vertices (links) that are in the same equivalence classes, i.e. they have the same properties of symmetry. The main definitions of group theory and examples of application of the new method of enumeration of inversions are presented. New results are obtained and divided in two classes: original results in non-planar screw systems (λ≠3) and results in agreement with a previously published list for planar kinematic chains and planar mechanisms (inversions). Two tables (1 and 3) are provided, which are up-to-date lists of kinematic chains and mechanisms for several screw systems.
12
KONDO, Koichi. "Collision avoidance by free space enumeration based on heuristic graph search." Journal of the Robotics Society of Japan 6, no. 6 (1988): 489–98. http://dx.doi.org/10.7210/jrsj.6.6_489.
Full text
13
Haiduc, Ionel. "A Graph-Based Classification and Enumeration of Inorganic Homo- And Heterocycles." Phosphorus, Sulfur, and Silicon and the Related Elements 64, no. 1-4 (January 1992): 169–78. http://dx.doi.org/10.1080/10426509208041143.
Full text
14
Kondo, Koichi. "Collision avoidance by free space enumeration based on heuristic graph search." Advanced Robotics 5, no. 3 (January 1990): 293–308. http://dx.doi.org/10.1163/156855391x00214.
Full text
15
Pospíchal, Jiří, and Vladimír Kvasnička. "An Alternative Approach for Constructive Enumeration of Graphs." Collection of Czechoslovak Chemical Communications 58, no. 4 (1993): 754–74. http://dx.doi.org/10.1135/cccc19930754.
Full textAbstract:
An efficient method for constructive enumeration of graphs is suggested. The method is based on the so called semicanonical numbering of graphs, that is a numbering much more restrictive than the cooperative numbering. Graph-theoretical properties of the semicanonical numbering make it possible to formulate an exhaustive and nonredundant constructive enumeration of graphs. The approach allows an easy introduction of specifications for molecular graphs.
16
Amiri, Behzad, Jorg Kliewer, and Lara Dolecek. "Analysis and Enumeration of Absorbing Sets for Non-Binary Graph-Based Codes." IEEE Transactions on Communications 62, no. 2 (February 2014): 398–409. http://dx.doi.org/10.1109/tcomm.2013.122113.130465.
Full text
17
HAIDUC, I. "ChemInform Abstract: A Graph-Based Classification and Enumeration of Inorganic Homo- and Heterocycles." ChemInform 23, no. 23 (August 22, 2010): no. http://dx.doi.org/10.1002/chin.199223012.
Full text
18
Prokopenkov, Vladymyr. "POLYNOMIAL ALGORITHM FOR FINDING A HAMILTONIAN CYCLE ON A GRAPH." Bulletin of NTU "KhPI". Series: Strategic management, portfolio, program and project management, no. 1(3) (April 17, 2021): 55–65. http://dx.doi.org/10.20998/2413-3000.2021.3.8.
Full textAbstract:
The subject of research is the solution of the problem of finding a Hamiltonian cycle on a graph, which in discrete mathematics belongs to the NP complexity class and still retains interest. The aim of this work is to develop a new algorithm for solving this problem, which guarantees finding the optimal solution with polynomial time. In [1], an analysis of the current state of the problem was performed, the shortcomings of existing methods of solving were noted, and new principles and method of finding solution were presented. Known methods for solving the problem are based on the implementation of a search of possible solutions or on intuitive heuristics. Enumeration methods of solutions are unacceptable in terms of costs, since they characterized by non-polynomial time. Heuristic methods are satisfactory in time, but they do not guarantee finding the optimal solution. The popularity of enumeration methods is explained by the linear simplicity of searching in a pre-known set of acceptable solutions to the problem. But the factorial dependence of the power of the set of solutions (n-1)! from the number of vertices of the graph n makes it impossible to use such methods for large-size problems in practice. The desire to significantly reduce time costs leads to attempts to reasonably reduce the enumeration set or to the development of various heuristics, which actually indicates that it is impossible to formulate conditions for finding the optimal solution to the problem as a whole. This article describes the conditions that determine the optimal solution of the problem and a polynomial algorithm for solving the problem that embodies the described method. Finding the optimal solution to the problem is reduced to finding a closed path in a new graph of shortest paths. The shortest paths graph built on the original graph of the problem by using Dijkstra's algorithm. The enumeration set for determining the optimal solution of the problem consists of solutions that are constructed from each vertex of the source graph in the shortest paths graph. The size of this set is estimated as n(n-1). The developed parallel algorithm guarantees finding the optimal solution, significantly reduces the initial search space, and allows you to find a solution with polynomial complexity. Testing of the program showed the efficiency of the developed method and algorithm for solving the problem.
19
Jeng, Shyr-Long, Rohit Roy, and Wei-Hua Chieng. "A Matrix Approach for Analyzing Signal Flow Graph." Information 11, no. 12 (November 30, 2020): 562. http://dx.doi.org/10.3390/info11120562.
Full textAbstract:
Mason’s gain formula can grow factorially because of growth in the enumeration of paths in a directed graph. Each of the (n − 2)! permutation of the intermediate vertices includes a path between input and output nodes. This paper presents a novel method for analyzing the loop gain of a signal flow graph based on the transform matrix approach. This approach only requires matrix determinant operations to determine the transfer function with complexity O(n3) in the worst case, therefore rendering it more efficient than Mason’s gain formula. We derive the transfer function of the signal flow graph to the ratio of different cofactor matrices of the augmented matrix. By using the cofactor expansion, we then obtain a correspondence between the topological operation of deleting a vertex from a signal flow graph and the algebraic operation of eliminating a variable from the set of equations. A set of loops sharing the same backward edges, referred to as a loop group, is used to simplify the loop enumeration. Two examples of feedback networks demonstrate the intuitive approach to obtain the transfer function for both numerical and computer-aided symbolic analysis, which yields the same results as Mason’s gain formula. The transfer matrix offers an excellent physical insight, because it enables visualization of the signal flow.
20
Chen, Wei, Jia Liu, Ziyang Chen, Xian Tang, and Kaiyu Li. "PBSM: An Efficient Top-K Subgraph Matching Algorithm." International Journal of Pattern Recognition and Artificial Intelligence 32, no. 06 (February 21, 2018): 1850020. http://dx.doi.org/10.1142/s0218001418500209.
Full textAbstract:
Top-K subgraph matching is one of the hot research issues in graph data management, which is to find, from the data graph, K subgraphs isomorphic to the query graph with the largest sum of weights. The existing methods of Top-K subgraph matching on large graphs usually use the filter-and-verify strategy. However, they all suffer from inefficiency in both stages. In the filtering stage, there exists repeated enumeration of vertices and the excessive memory cost of the filtering. In the verification stage, there exists redundant verification. Regarding to the above problems, we propose to use the preprocessing of the graph compression based on equivalent vertices to reduce the enumeration. In the filtering stage, we propose to reduce the memory cost by only considering the direct neighbors. In the verification stage, we take the vertex with the minimum number of candidate vertices in the query graph as the start vertex of the matching order, and use the idea of Ranking While Matching (RWM) to terminate the execution of the algorithm as early as possible by estimating the upper bound of the weights, so as to reduce redundant verification and improve the overall performance. Finally, the experimental results show that our method is much more efficient than existing methods in compression and the processing time.
21
Deptuła, Adam, Józef Drewniak, and Marian A. Partyka. "Analysis of a planetary gear modeled with a contour graph taking into account the method of parametric play structures." Mechanik 90, no. 7 (July 10, 2017): 640–42. http://dx.doi.org/10.17814/mechanik.2017.7.98.
Full textAbstract:
Previous applications of the graph theory concerned the modeling of gears for dynamic analysis, kinematic analysis, synthesis, structural analysis, gearshift optimization and automatic design based on so-called graph grammars. Some tasks can be performed only by using methods resulting from a graph theory, e.g. enumeration of structural solutions. The contour plot method consists in distinguishing a series of consecutive rigid units of the mechanism, forming a closed loop (so-called contour). At a later stage, it is possible to analyze the obtained contour graph as a directed graph of dependence. The work presents an example of the use of game-tree structures for describing the contour graph of a planetary gear. As a result of the decomposition of the graph in the dependence on each of the vertices, game-tree structures are obtained, which allow calculate algorithmically.
22
Kim, Donghyun, Hao Guo, Wei Wang, Joong-Lyul Lee, Sung-Sik Kwon, and Alade O. Tokuta. "On efficient vaccine distribution strategy to suppress pandemic using social relation." Discrete Mathematics, Algorithms and Applications 08, no. 01 (February 26, 2016): 1650010. http://dx.doi.org/10.1142/s1793830916500105.
Full textAbstract:
In this paper, we investigate the problem of how to distribute vaccines, which will be supplied over time, so that the number of the infected can be minimized during a given mission period. The concept of temporal graph is adopted to abstract the constantly changing social relations over time. Then, we formally introduce the social-relation-based vaccine distribution planning problem (SVDP2) on the temporal graph. To solve the problem, we first introduce a new graph induction technique to combine the subgraphs in the temporal graph into a single directed acyclic graph. Then, we design a new technique based on a maximum flow algorithm to evaluate the quality of any feasible solution of the problem. Finally, we propose an enumeration algorithm which will search the solution space using the evaluation technique and find the best possible solution within polynomial time. Our simulation result shows the proposed algorithm is more efficient than a simple strategy which randomly distributes vaccines.
23
Hao, Kongzhang, Long Yuan, and Wenjie Zhang. "Distributed hop-constrained s-t simple path enumeration at billion scale." Proceedings of the VLDB Endowment 15, no. 2 (October 2021): 169–82. http://dx.doi.org/10.14778/3489496.3489499.
Full textAbstract:
Hop-constrained s-t simple path (HC-s-t path) enumeration is a fundamental problem in graph analysis and has received considerable attention recently. Straightforward distributed solutions are inefficient and suffer from poor scalabiltiy when addressing this problem in billion-scale graphs due to the disability of pruning fruitless exploration or huge memory consumption. Motivated by this, in this paper, we aim to devise an efficient and scalable distributed algorithm to enumerate the HC-s-t paths in billion-scale graphs. We first propose a new hybrid search paradigm tailored for HC-s-t path enumeration. Based on the new search paradigm, we devise a distributed enumeration algorithm following the divide-and-conquer strategy. The algorithm can not only prune fruitless exploration, but also well bound the memory consumption with high parallelism. We also devise an effective workload balance mechanism that is automatically triggered by the idle machines to handle skewed workloads. Moreover, we explore the bidirectional search strategy to further improve enumeration efficiency. The experiment results demonstrate the efficiency of our proposed algorithm.
24
IVANOV, DENIS, and ALEXANDER SEMENOV. "TOPOLOGICAL APPROACH TO BLACKHOLES ANOMALY DETECTION IN DIRECTED NETWORKS." Computational nanotechnology 7, no. 2 (June 30, 2020): 49–57. http://dx.doi.org/10.33693/2313-223x-2020-7-2-49-57.
Full textAbstract:
In this paper we consider the problem of finding a blackhole pattern in directed unweighted graphs. The problem statement is the same as in an original paper by scientists from University of New-Jersey published in 2010. The paper contributes to the special graph pattern matching, the work results can be used for anomaly detection in finances, natural disasters, urban analysis. This paper aims to propose a novel algorithm for blackhole mining, which would take into account inner structure of the “blackhole” pattern and utilize this knowledge for more efficient mining. This paper reviews previously published solutions and tests them on larger graphs containing up to 1 million of nodes. In particular, an iBlackhole algorithm and its Divide and Conquer modification iBlackholeDC are considered, their weak spots are highlighted and reviewed upon. Graph condensation is introduced as an efficient preprocessing for the problem. This paper provides theorems and definitions describing inner structure of the blackhole pattern. Based on the new theorems, a new approach to enumeration of candidates is introduced as well as rules and heuristics aiming for faster filtration of candidates: they utilize topological sorting of a graph and definition of a “special” node, which is also introduced in this paper. Special nodes properties are described. We propose a novel TopSortBH algorithm. It consists of the graph condensation, candidates enumeration and heuristics for candidates filtration. The algorithm is provided with modification called FastSkip, which allows for more aggressive filtering strategy in time-sensitive cases. All mentioned algorithms are implemented and tested on the IBM Power8 based system. Experimental results show efficiency of the condensation as graph preprocessing for the problem. Strong advantage in found blackholes count is demonstrated for TopSortBH in comparison to iBlackholeDC on RMAT, SSCA2 and UR graphs containing up to 1 million nodes.
25
Zhu, Wanlin, Minglei Fang, and Xianya Geng. "Enumeration of the Gutman and Schultz indices in the random polygonal chains." Mathematical Biosciences and Engineering 19, no. 11 (2022): 10826–45. http://dx.doi.org/10.3934/mbe.2022506.
Full textAbstract:
<abstract><p>The Gutman index and Schultz index of a connected graph are degree-distance-based topological indices. In this paper, we devoted to establish the explicit analytical expressions for the simple formulae of the expected values of the Gutman and Schultz indices in a random polygonal. Based on these results above, we get the extremal values and average values of Gunman and Schultz indices of all polygonal chains.</p></abstract>
26
Lawall, Alexander, and Thomas Schaller. "A Graph-based and Declarative Approach to a Secure Resource Management in Smart Factories." International Journal on Cryptography and Information Security 12, no. 3 (September 30, 2022): 1–11. http://dx.doi.org/10.5121/ijcis.2022.12301.
Full textAbstract:
The article presents an applied research using the Design Science Research Methodology for securely managing resources of smart factories via a graph-based approach combined with a declarative query language. This query language can be used to find appropriate production facilities that are able to fulfill specific manufacturing tasks. This approach is aimed to solve the problem with the management effort for production facilities using enumeration for naming these facilities for the manufacturing tasks. Thus, the security is ensured by identifying the “current” valid identities (resources). Additionally, the usage of deputy relationships leads to alternative production facilities if resources have a breakdown or have to be serviced which has an effect on the availability.
27
Shang, Yilun. "On the number of spanning trees, the Laplacian eigenvalues, and the Laplacian Estrada index of subdivided-line graphs." Open Mathematics 14, no. 1 (January 1, 2016): 641–48. http://dx.doi.org/10.1515/math-2016-0055.
Full textAbstract:
Abstract As a generalization of the Sierpiński-like graphs, the subdivided-line graph Г(G) of a simple connected graph G is defined to be the line graph of the barycentric subdivision of G. In this paper we obtain a closed-form formula for the enumeration of spanning trees in Г(G), employing the theory of electrical networks. We present bounds for the largest and second smallest Laplacian eigenvalues of Г(G) in terms of the maximum degree, the number of edges, and the first Zagreb index of G. In addition, we establish upper and lower bounds for the Laplacian Estrada index of Г(G) based on the vertex degrees of G. These bounds are also connected with the number of spanning trees in Г(G).
28
Nazarov, Vadim Igorevich, and Eduard Stanislavovich Klyshinsky. "Graph-based data structure for enumeration of all possible generation scenarios of immune receptor sequences." Keldysh Institute Preprints, no. 108 (2017): 1–30. http://dx.doi.org/10.20948/prepr-2017-108.
Full text
29
Jamshidi, Kasra, and Keval Vora. "A Deeper Dive into Pattern-Aware Subgraph Exploration with PEREGRINE." ACM SIGOPS Operating Systems Review 55, no. 1 (June 2, 2021): 1–10. http://dx.doi.org/10.1145/3469379.3469381.
Full textAbstract:
Graph mining workloads aim to extract structural properties of a graph by exploring its subgraph structures. PEREGRINE is a general-purpose graph mining system that provides a generic runtime to efficiently explore subgraph structures of interest and perform various graph mining analyses. It takes a 'pattern-aware' approach by incorporating a pattern-based programming model along with efficient pattern matching strategies. The programming model enables easier expression of complex graph mining use cases and enables PEREGRINE to extract the semantics of patterns. By analyzing the patterns, PEREGRINE generates efficient exploration plans which it uses to guide its subgraph exploration. In this paper, we present an in-depth view of the patternanalysis techniques powering the matching engine of PEREGRINE. Beyond the theoretical foundations from prior research, we expose opportunities based on how the exploration plans are evaluated, and develop key techniques for computation reuse, enumeration depth reduction, and branch elimination. Our experiments show the importance of patternawareness for scalable and performant graph mining where the presented new techniques speed up the performance by up to two orders of magnitude on top of the benefits achieved from the prior theoretical foundations that generate the initial exploration plans.
30
Xue, Hui-Ling, Geng Liu, and Xiao-Hui Yang. "A review of graph theory application research in gears." Proceedings of the Institution of Mechanical Engineers, Part C: Journal of Mechanical Engineering Science 230, no. 10 (April 16, 2015): 1697–714. http://dx.doi.org/10.1177/0954406215583321.
Full textAbstract:
Graph theory has been applied to gear train analysis and synthesis for many years, and it is an effective and systematic modeling approach in the design process of gear transmission. Based on more than 100 references listed in this paper, a review about the graph-based method for kinematic and static force analysis, power flow, and mechanical efficiency computation is presented. The method is based on the concept of fundamental circuit corresponding to a basic epicyclic gear train. A 1-dof epicyclic gear train and a two-stage planetary gear train are used to illustrate the application of this method. Besides, isomorphism identification in the synthesis process and enumeration of 1-dof epicyclic gear train graphs are surveyed particularly. Also, the computerized methods for detection of redundant gears and degenerate structures in epicyclic gear trains are reviewed, respectively.
31
Batenkov, Kirill. "Accurate and Boundary Estimate of Communication Network Connectivity Probability Based on Model State Complete Enumeration Method." SPIIRAS Proceedings 18, no. 5 (September 19, 2019): 1093–118. http://dx.doi.org/10.15622/sp.2019.18.5.1093-1118.
Full textAbstract:
We consider one of communication network structure analysis and synthesis methods, based on the simplest approach to connectivity probability calculation – a method of full network typical state search. In this case, the typical states of the network are understood as the events of network graph connectivity and disconnection, which are simple graph chains and sections. Despite significant drawback of typical state enumeration method, which involves significant calculation complexity, it is quite popular at stage of debugging new analysis methods. In addition, on its basis it is possible to obtain boundary estimates of network connectivity probability. Thus, when calculating Asari–Proshana boundaries use full set of incoherent (top) and cohesive (bottom) communication network states. These boundaries are based on statement that network connectivity probability under same conditions is higher (lower) than that of network composed of independent disjoint (connected) subgraph complete set serial (parallel) connection. When calculating Litvak–Ushakov boundaries, only edge-disjoint sections (for upper) and connected subgraphs (for lower) are used, i.e. subsets of elements such that any element does not meet two-rods. This boundary takes into account the well-known natural monotonicity property, which is to reduce (increase) network reliability with decrease (increase) any element reliability. From a computational view point Asari–Proshana boundaries have huge drawback: they require references of all connected subgraphs to compute upper bounds and all minimal cuts for bottom, which in itself is non-trivial. Litvak–Ushakov boundaries are devoid of these drawback: by calculating them, we can stop at any searching step for variants of sets of independent connected and disconnected graph states.
32
Prokopenkov, Vladymyr. "DEFERRED SOLUTIONS METHOD DEVELOPMENT FOR CONSTRUCTING A HAMILTONIAN CYCLE SEARCH ALGORITHM ON A GRAPH." Bulletin of NTU "KhPI". Series: Strategic management, portfolio, program and project management, no. 1(5) (July 31, 2022): 44–49. http://dx.doi.org/10.20998/2413-3000.2022.5.
Full textAbstract:
The subject of research is the solution of the problem of finding a Hamiltonian cycle on a graph, which belongs to the NP complexity class. The aim of the work is to develop an effective polynomial algorithm for its optimal solution. The paper analyzes the problem and the existing methods of its solution, identifies the shortcomings of these methods. It is showing that the main obstacle remains the inability to formulate the conditions for finding the optimal solution. As a result, the methods for solving this problem based on enumeration over acceptable solutions or on intuitive heuristics. Heuristic methods do not guarantee finding the optimal solution. Enumeration methods are popular because of a simple linear search scheme in a pre-known set of valid solutions to the problem. They allow you to find the optimal solution, but require a lot of time. In enumeration algorithms, valid solutions can be obtain by using graph traversal algorithms, but the factorial cost of enumeration requires reducing the enumeration space, for example, using the branch-and-bound method. This method is based on an ordered search of acceptable solutions, considering only the most promising ones, and discarding at once the whole sets of solutions that are not such. For the method to work, it is important to determine the cost function of a partial solution that depends on certain parameters, which is difficult, and perhaps impossible for the problem under consideration. If the function generates a probabilistic estimate, there is a risk of losing the optimal solution to the problem when it is discarding. The only reliable estimate for a valid solution is the length of the cycle, which, unfortunately, becoming known after its formation. As an alternative, the article proposes a new method of deferred solutions, according to which all possible partial solutions are constructed and stored simultaneously. Each partial solution is characterizing by its own evaluation. At each step, a partial solution is completing by adding a vertex to it, to which you can go from its last vertex – as many new partial solutions are building, as there are options for going from its last vertex. The generated partial solutions are saving, and the current worked-out solution is deleting. To perform the next step, the partial solution that has the smallest length estimate is selecting. Execution continues until the optimal solution is not build. The proposed method solves the problem under consideration, but its application for large graphs requires the selection of a correct estimate of partial solutions.
33
PELLEGRINI, FRANÇOIS. "BOUNDS FOR THE BANDWIDTH OF THE d-ARY DE BRUIJN GRAPH." Parallel Processing Letters 03, no. 04 (December 1993): 431–43. http://dx.doi.org/10.1142/s0129626493000460.
Full textAbstract:
The computation of upper bounds of the bandwidth of graphs is mainly based on the giving of a numbering which achieves these bounds. In [9], Harper proposed such a numbering for the binary hypercube, based on the Hamming weights and binary values of the hypercube vertices. By defining an extended Hamming weight, this numbering can lead to an equivalent proof for the d-ary de Bruijn graph. We present in this paper an approach, based on the use of the continuous domain and Laplace’s theorem for asymptotically evaluating integrals, which leads to the enumeration of the vertices of the same extended Hamming weight in the non-binary case. This result allows the computation of an upper bound of the bandwidth of the unoriented de Bruijn graph, as well as an upper bound of its vertex-bisection when both the diameter and the degree are even.
34
Bannach, Max, and Sebastian Berndt. "Recent Advances in Positive-Instance Driven Graph Searching." Algorithms 15, no. 2 (January 27, 2022): 42. http://dx.doi.org/10.3390/a15020042.
Full textAbstract:
Research on the similarity of a graph to being a tree—called the treewidth of the graph—has seen an enormous rise within the last decade, but a practically fast algorithm for this task has been discovered only recently by Tamaki (ESA 2017). It is based on dynamic programming and makes use of the fact that the number of positive subinstances is typically substantially smaller than the number of all subinstances. Algorithms producing only such subinstances are called positive-instance driven (PID). The parameter treedepth has a similar story. It was popularized through the graph sparsity project and is theoretically well understood—but the first practical algorithm was discovered only recently by Trimble (IPEC 2020) and is based on the same paradigm. We give an alternative and unifying view on such algorithms from the perspective of the corresponding configuration graphs in certain two-player games. This results in a single algorithm that can compute a wide range of important graph parameters such as treewidth, pathwidth, and treedepth. We complement this algorithm with a novel randomized data structure that accelerates the enumeration of subproblems in positive-instance driven algorithms.
35
Mosterman, P. J. "HYBRSIM—a modelling and simulation environment for hybrid bond graphs." Proceedings of the Institution of Mechanical Engineers, Part I: Journal of Systems and Control Engineering 216, no. 1 (February 1, 2002): 35–46. http://dx.doi.org/10.1243/0959651021541417.
Full textAbstract:
Bond graphs are a powerful formalism to model continuous dynamics of physical systems. Hybrid bond graphs introduce an ideal switching element, the controlled junction, to approximate continuous behaviour that is too complex for numerical analysis (e.g. because of non-linearities or steep gradients). HYBRSIM is a tool for hybrid bond graph modelling and simulation implemented in Java and is documented in this paper. It performs event detection and location based on a bisectional search, handles run-time causality changes, including derivative causality, performs physically consistent (re-)initialization and supports two types of event iteration because of dynamic coupling. It exports hybrid bond graph models in Java and C/C++ code that includes discontinuities as switched equations (i.e. pre-enumeration is not required).
36
MADABHUSHI, S. V. R., S. LAKSHMIVARAHAN, and S. K. DHALL. "ANALYSIS OF A CLASS OF NETWORKS BASED ON CUBIC STAR GRAPHS." Journal of Circuits, Systems and Computers 04, no. 02 (June 1994): 191–222. http://dx.doi.org/10.1142/s0218126694000120.
Full textAbstract:
A new class of interconnection networks based on a family of graphs, called cubic graphs are introduced. These latter graphs arise as Cayley graphs of certain subgroups of the symmetric group. It turns out that these Cayley graphs are a hybrid between the binary hypercube and the star graph, and hence are called cubic star graphs, and are denoted by CS(m, n), m≥1 and n≥1. CS(m, n) inherits several of the properties of the hypercube and the star graph. In this paper, we present an analysis of the symmetric and topological properties. In particular, it is shown that CS(m, n) is edge transitive and hence maximally fault tolerant. We give an algorithm for finding the shortest path and provide an enumeration of the node disjoint paths. Optimal algorithms for single source and all-source broadcasting (also called gossiping) are derived. It is shown that CS(m, n) is Hamiltonian and interesting embeddings of several cycles, grids, and binary trees are derived. The paper concludes with a comparison of CS(m, n) with the binary hypercube and the star graph.
37
Yang, Jianye, Yun Peng, and Wenjie Zhang. "(p,q)-biclique counting and enumeration for large sparse bipartite graphs." Proceedings of the VLDB Endowment 15, no. 2 (October 2021): 141–53. http://dx.doi.org/10.14778/3489496.3489497.
Full textAbstract:
In this paper, we study the problem of ( p , q)-biclique counting and enumeration for large sparse bipartite graphs. Given a bipartite G = ( U, V , E), and two integer parameters p and q, we aim to efficiently count and enumerate all (p, q)-bicliques in G , where a (p, q)-biclique B ( L, R ) is a complete subgraph of G with L ⊆ U, R ⊆ V , |L| = p, and |R| = q. The problem of (p, q)-biclique counting and enumeration has many applications, such as graph neural network information aggregation, densest subgraph detection, and cohesive subgroup analysis, etc. Despite the wide range of applications, to the best of our knowledge, we note that there is no efficient and scalable solution to this problem in the literature. This problem is computationally challenging, due to the worst-case exponential number of (p, q)-bicliques. In this paper, we propose a competitive branch-and-bound baseline method, namely BCList, which explores the search space in a depth-first manner, together with a variety of pruning techniques. Although BCList offers a useful computation framework to our problem, its worst-case time complexity is exponential to p + q. To alleviate this, we propose an advanced approach, called BCList++. Particularly, BCList++ applies a layer based exploring strategy to enumerate ( p, q )-bicliques by anchoring the search on either U or V only, which has a worst-case time complexity exponential to either p or q only. Consequently, a vital task is to choose a layer with the least computation cost. To this end, we develop a cost model, which is built upon an unbiased estimator for the density of 2-hop graph induced by U or V. To improve computation efficiency, BCList++ exploits pre-allocated arrays and vertex labeling techniques such that the frequent subgraph creating operations can be substituted by array element switching operations. We conduct extensive experiments on 16 real-life datasets, and the experimental results demonstrate that BCList++ significantly outperforms the baseline methods by up to 3 orders of magnitude. We show via a case study that (p, q)-bicliques optimize the efficiency of graph neural networks.
38
Liu, T. S., and C. C. Chou. "Type Synthesis of Vehicle Planar Suspension Mechanism Using Graph Theory." Journal of Mechanical Design 115, no. 3 (September 1, 1993): 652–57. http://dx.doi.org/10.1115/1.2919240.
Full textAbstract:
This paper presents a graph theory-based approach to optimum type synthesis of vehicle suspension mechanisms using an expert system. Kinematic chain isomorphism is identified, using an extended degree method to facilitate the enumeration of kinematic structures. Rules representing design criteria and the flow value theory based on energy loss calculation are incorporated in the rule base to evaluate and select mechanisms among those that are enumerated in the database. Statistical variance calculation serves to complement the flow value theory. A new method called the extended flow value method is devised for isomorphism checking of labeled graphs. In the spirit of increasing emphasis on the riding quality of vehicles, several novel suspension configurations are created to ensure maintenance ease and vibration damping efficiency.
39
Dekker, David, David Krackhardt, and Tom A. B. Snijders. "Transitivity correlation: A descriptive measure of network transitivity." Network Science 7, no. 3 (September 2019): 353–75. http://dx.doi.org/10.1017/nws.2019.32.
Full textAbstract:
AbstractThis paper proposes that common measures for network transitivity, based on the enumeration of transitive triples, do not reflect the theoretical statements about transitivity they aim to describe. These statements are often formulated as comparative conditional probabilities, but these are not directly reflected by simple functions of enumerations. We think that a better approach is obtained by considering the probability of a tie between two randomly drawn nodes, conditional on selected features of the network. Two measures of transitivity based on correlation coefficients between the existence of a tie and the existence, or the number, of two-paths between the nodes are developed, and called “Transitivity Phi” and “Transitivity Correlation.” Some desirable properties for these measures are studied and compared to existing clustering coefficients, in both random (Erdös–Renyi) and in stylized networks (windmills). Furthermore, it is shown that in a directed graph, under the condition of zero Transitivity Correlation, the total number of transitive triples is determined by four underlying features: size, density, reciprocity, and the covariance between in- and outdegrees. Also, it is demonstrated that plotting conditional probability of ties, given the number of two-paths, provides valuable insights into empirical regularities and irregularities of transitivity patterns.
40
Wang, Zibo, Yaofang Zhang, Zhiyao Liu, Xiaojie Wei, Yilu Chen, and Bailing Wang. "An Automatic Planning-Based Attack Path Discovery Approach from IT to OT Networks." Security and Communication Networks 2021 (October 31, 2021): 1–18. http://dx.doi.org/10.1155/2021/1444182.
Full textAbstract:
With the convergence of IT and OT networks, more opportunities can be found to destroy physical processes by cyberattacks. Discovering attack paths plays a vital role in describing possible sequences of exploitation. Automated planning that is an important branch of artificial intelligence (AI) is introduced into the attack graph modeling. However, while adopting the modeling method for large-scale IT and OT networks, it is difficult to meet urgent demands, such as scattered data management, scalability, and automation. To that end, an automatic planning-based attack path discovery approach is proposed in this paper. At first, information of the attacking knowledge and network topology is formally represented in a standardized planning domain definition language (PDDL), integrated into a graph data model. Subsequently, device reachability graph partitioning algorithm is introduced to obtain subgraphs that are small enough and of limited size, which facilitates the discovery of attack paths through the AI planner as soon as possible. In order to further cope with scalability problems, a multithreading manner is used to execute the attack path enumeration for each subgraph. Finally, an automatic workflow with the assistance of a graph database is provided for constructing the PDDL problem file for each subgraph and traversal query in an interactive way. A case study is presented to demonstrate effectiveness of attack path discovery and efficiency with the increase in number of devices.
41
Ou, Feng-Ming, Hong-Sen Yan, and Ming-Feng Tang. "THE SYNTHESIS OF MECHANISM SYSTEMS USING A MECHANISM CONCEPT LIBRARY." Transactions of the Canadian Society for Mechanical Engineering 34, no. 1 (March 2010): 151–63. http://dx.doi.org/10.1139/tcsme-2010-0010.
Full textAbstract:
This paper presents an approach for synthesizing all possible mechanism systems of kinematic building blocks in a mechanism concept library. The kinematic building blocks are defined as SISO primitive mechanisms, and their serial and/or parallel combinations are expressed as corresponding out-trees based on graph representation. By representing the constructive building blocks as labeled vertices and their possible combination relationships as directed edges, the synthesis approach is developed by adopting graph enumeration theorem. An illustrative example of four kinematic building blocks, including two crank-rocker linkages and two slider-crank mechanisms, is provided to validate the presented approach. The result shows that all feasible mechanism systems can be obtained effectively by following the synthesis method and which provides more alternatives in the library during design or re-design of mechanisms.
42
Chen, Yong Heng, Wan Li Zuo, and Feng Lin He. "Optimization Strategy of Bidirectional Join Enumeration in Multi-Core CPUS." Applied Mechanics and Materials 44-47 (December 2010): 383–87. http://dx.doi.org/10.4028/www.scientific.net/amm.44-47.383.
Full textAbstract:
Most contemporary database systems query optimizers exploit System-R’s Bottom-up dynamic programming method (DP) to find the optimal query execution plan (QEP) without evaluating redundant sub-plans. As modern microprocessors employ multiple cores to accelerate computations, the parallel optimization algorithm has been proposed to parallelize the Bottom-up DP query optimization process. However Top-down DP method can derive upper bounds for the costs of the plans it generates which is not available to typical Bottom-up DP method since such method generate and cost all subplans before considering larger containing plans. This paper combined the enhancements of two approaches and proposes a comprehensive and practical algorithm based graph-traversal driven, referred to here as DPbid, for parallelizing query optimization in the multi-core processor architecture. This paper has implemented such a search strategy and experimental results show that can improve optimization time effective compared to known existing algorithms.
43
Chang, Yi-Jun, Seth Pettie, Thatchaphol Saranurak, and Hengjie Zhang. "Near-optimal Distributed Triangle Enumeration via Expander Decompositions." Journal of the ACM 68, no. 3 (May 13, 2021): 1–36. http://dx.doi.org/10.1145/3446330.
Full textAbstract:
We present improved distributed algorithms for variants of the triangle finding problem in the model. We show that triangle detection, counting, and enumeration can be solved in rounds using expander decompositions . This matches the triangle enumeration lower bound of by Izumi and Le Gall [PODC’17] and Pandurangan, Robinson, and Scquizzato [SPAA’18], which holds even in the model. The previous upper bounds for triangle detection and enumeration in were and , respectively, due to Izumi and Le Gall [PODC’17]. An -expander decomposition of a graph is a clustering of the vertices such that (i) each cluster induces a subgraph with conductance at least and (ii) the number of inter-cluster edges is at most . We show that an -expander decomposition with can be constructed in rounds for any and positive integer . For example, a -expander decomposition only requires rounds to compute, which is optimal up to subpolynomial factors, and a -expander decomposition can be computed in rounds, for any arbitrarily small constant . Our triangle finding algorithms are based on the following generic framework using expander decompositions, which is of independent interest. We first construct an expander decomposition. For each cluster, we simulate algorithms with small overhead by applying the expander routing algorithm due to Ghaffari, Kuhn, and Su [PODC’17] Finally, we deal with inter-cluster edges using recursive calls.
44
Dias, Ana Paula S., and Eliana Manuel Pinho. "Enumerating periodic patterns of synchrony via finite bidirectional networks." Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 466, no. 2115 (November 16, 2009): 891–910. http://dx.doi.org/10.1098/rspa.2009.0404.
Full textAbstract:
Periodic patterns of synchrony are lattice networks whose cells are coloured according to a local rule, or balanced colouring, and such that the overall system has spatial periodicity. These patterns depict the finite-dimensional flow-invariant subspaces for all the lattice dynamical systems, in the given lattice network, that exhibit those periods. Previous results relate the existence of periodic patterns of synchrony, in n -dimensional Euclidean lattice networks with nearest neighbour coupling architecture, with that of finite coupled cell networks that follow the same colouring rule and have all the couplings bidirectional. This paper addresses the relation between periodic patterns of synchrony and finite bidirectional coloured networks. Given an n -dimensional Euclidean lattice network with nearest neighbour coupling architecture, and a colouring rule with k colours, we enumerate all the periodic patterns of synchrony generated by a given finite network, or graph. This enumeration is constructive and based on the automorphisms group of the graph.
45
Pavlenko, Yevhen, Vladimir Butenko, Vadim Gubin, and Serhii Lubenets. "RESEARCH OF DATA TYPE CLASSIFICATION METHODS WHEN DEVELOPING COMPUTER ENGINEERING SOFTWARE." Bulletin of National Technical University "KhPI". Series: System Analysis, Control and Information Technologies, no. 1 (5) (July 12, 2021): 80–85. http://dx.doi.org/10.20998/2079-0023.2021.01.13.
Full textAbstract:
The paper deals with the problems of increasing the efficiency of software development, in particular, the issue of reducing the time for developing programs and using automated synthesis of programs, which will avoid the revision of the original product. The software should be tested along with other system components in all combinations that may occur. Testing is time-consuming because hidden bugs are revealed through unexpected interactions between software components. With structural analysis, data flow diagrams are not the end result, they are a developer tool. First, diagrams are built, and then mechanisms are developed to ensure the required system behavior. A graphical approach to solving the problem of automation of software development is being developed, based on the involvement of visual forms of program presentation. For any program object, you can select a finite number of states in which it is at each moment of time. The program progress is associated with the transition of an object from one state to another. The graph replaces the textual form of the description of the program algorithm, while the visual representation of the algorithm is realized. The specification of data structures, as well as the setting of intermodular interfaces according to data, is separated from the description of the structure of the algorithm and controls. Basic modules and data types are used. Basic modules are local calculable functions, on the basis of which all other technology objects are generated. Data types describe the syntactic and semantic aspects of constructing data used in base functions. Algorithms for finding routes on directed graphs are considered. When defining routes from the root vertex to the final ones, the properties of the algebra of three-valued logic were used. Based on the considered approach, as well as taking into account its shortcomings, a method for classifying data types was proposed, based on the implementation of a partial enumeration of the routes of the graph of program links and a method for designing software based on it, taking into account minimizing the time and cost of the project.
Keywords: software, computer engineering, information systems, components, partial enumeration of graph routes, development costs.
46
Montes, Carlos, Zoran Kapelan, and Juan Saldarriaga. "Impact of Self-Cleansing Criteria Choice on the Optimal Design of Sewer Networks in South America." Water 11, no. 6 (May 31, 2019): 1148. http://dx.doi.org/10.3390/w11061148.
Full textAbstract:
This paper aims to analyze different sediment self-cleansing criteria and to find out what the corresponding implications are on the optimal design of sewer systems. A methodology based on enumeration is used to find the sewer network design that minimizes the costs of construction while fulfilling a number of design criteria including self-cleansing constraints. Three stormwater and wastewater sewer networks are used for the analyses. The results indicate that in cases where the terrain slopes and design flow rates are higher, the self-cleansing restrictions are irrelevant to the optimal design. However, when the terrain slopes and the design flow rates are lower, these restrictions affect the final design. Using the results obtained, a graph is constructed showing the limit at which self-cleansing restrictions become a constraining parameter in optimal design for sewer networks. It is expected that this graph will be useful for the design of future sewer networks in low-income areas, where the design of traditional, gravity-based sewer systems is essential.
47
Hasan, Zafar, and Maciej J. Ciesielski. "FSM Decomposition and Functional Verification of FSM Networks." VLSI Design 3, no. 3-4 (January 1, 1995): 249–65. http://dx.doi.org/10.1155/1995/62636.
Full textAbstract:
Here we present a new method for the decomposition of a Finite State Machine (FSM) into a network of interacting FSMs and a framework for the functional verification of the FSM network at different levels of abstraction. The problem of decomposition is solved by output partitioning and state space decomposition using a multiway graph partitioning technique. The number of submachines is determined dynamically during the partitioning process. The verification algorithm can be used to verify (a) the result of FSM decomposition on a behavioral level, (b) the encoded FSM network, and (c) the FSM network after logic optimization. Our verification technique is based on an efficient enumeration-simulation method which involves traversal of the state transition graph of the prototype machine and simulation of the decomposed machine network. Both the decomposition and verification/simulation algorithms have been implemented as part of an interactive FSM synthesis system and tested on a set of benchmark examples.
48
DANIEL, FREDERIC, and GERARD AUTHIÉ. "SHORTEST PATHS MULTIPLICITY IN GENERALIZED DE BRUIJN AND KAUTZ NETWORKS." Parallel Processing Letters 03, no. 04 (December 1993): 363–74. http://dx.doi.org/10.1142/s012962649300040x.
Full textAbstract:
Generalized de Bruijn and Kautz networks are important since they allow networks of any size with vertices of fixed degree. Communication issues are related to easy construction/enumeration of shortest paths between vertex-couples. An easy method based on residue calculation is introduced to find multiple shortest paths if they exist, allowing better communication schemes. The main results concern the properties of multiple shortest paths (especially disjunction) and the number of vertex-couples separated by several shortest paths as a function of the graph size. Conditions to get or avoid networks with multiple shortest paths are proposed which can be useful for the design of communication schemes.
49
Şeker, Oylum, Pinar Heggernes, Tinaz Ekim, and Z. Caner Taşkın. "Generation of random chordal graphs using subtrees of a tree." RAIRO - Operations Research 56, no. 2 (March 2022): 565–82. http://dx.doi.org/10.1051/ro/2022027.
Full textAbstract:
Chordal graphs form one of the most studied graph classes. Several graph problems that are NP-hard in general become solvable in polynomial time on chordal graphs, whereas many others remain NP-hard. For a large group of problems among the latter, approximation algorithms, parameterized algorithms, and algorithms with moderately exponential or sub-exponential running time have been designed. Chordal graphs have also gained increasing interest during the recent years in the area of enumeration algorithms. Being able to test these algorithms on instances of chordal graphs is crucial for understanding the concepts of tractability of hard problems on graph classes. Unfortunately, only few published papers give algorithms for generating chordal graphs. Even in these papers, only very few methods aim for generating a large variety of chordal graphs. Surprisingly, none of these methods is directly based on the “intersection of subtrees of a tree” characterization of chordal graphs. In this paper, we give an algorithm for generating chordal graphs, based on the characterization that a graph is chordal if and only if it is the intersection graph of subtrees of a tree. Upon generating a random host tree, we give and test various methods that generate subtrees of the host tree. We compare our methods to one another and to existing ones for generating chordal graphs. Our experiments show that one of our methods is able to generate the largest variety of chordal graphs in terms of maximal clique sizes. Moreover, two of our subtree generation methods result in an overall complexity of our generation algorithm that is the best possible time complexity for a method generating the entire node set of subtrees in an “intersection of subtrees of a tree” representation. The instances corresponding to the results presented in this paper, and also a set of relatively small-sized instances are made available online.
50
Azam, Naveed Ahmed, Aleksandar Shurbevski, and Hiroshi Nagamochi. "An Efficient Algorithm to Count Tree-Like Graphs with a Given Number of Vertices and Self-Loops." Entropy 22, no. 9 (August 22, 2020): 923. http://dx.doi.org/10.3390/e22090923.
Full textAbstract:
Graph enumeration with given constraints is an interesting problem considered to be one of the fundamental problems in graph theory, with many applications in natural sciences and engineering such as bio-informatics and computational chemistry. For any two integers n≥1 and Δ≥0, we propose a method to count all non-isomorphic trees with n vertices, Δ self-loops, and no multi-edges based on dynamic programming. To achieve this goal, we count the number of non-isomorphic rooted trees with n vertices, Δ self-loops and no multi-edges, in O(n2(n+Δ(n+Δ·min{n,Δ}))) time and O(n2(Δ2+1)) space, since every tree can be uniquely viewed as a rooted tree by either regarding its unicentroid as the root, or in the case of bicentroid, by introducing a virtual vertex on the bicentroid and assuming the virtual vertex to be the root. By this result, we get a lower bound and an upper bound on the number of tree-like polymer topologies of chemical compounds with any “cycle rank”.