Cycle basis

Last updated
The symmetric difference of two cycles is an Eulerian subgraph Cycle space addition.svg
The symmetric difference of two cycles is an Eulerian subgraph

In graph theory, a branch of mathematics, a cycle basis of an undirected graph is a set of simple cycles that forms a basis of the cycle space of the graph. That is, it is a minimal set of cycles that allows every even-degree subgraph to be expressed as a symmetric difference of basis cycles.

Contents

A fundamental cycle basis may be formed from any spanning tree or spanning forest of the given graph, by selecting the cycles formed by the combination of a path in the tree and a single edge outside the tree. Alternatively, if the edges of the graph have positive weights, the minimum weight cycle basis may be constructed in polynomial time.

In planar graphs, the set of bounded cycles of an embedding of the graph forms a cycle basis. The minimum weight cycle basis of a planar graph corresponds to the Gomory–Hu tree of the dual graph.

Definitions

A spanning subgraph of a given graph G has the same set of vertices as G itself but, possibly, fewer edges. A graph G, or one of its subgraphs, is said to be Eulerian if each of its vertices has even degree (its number of incident edges). Every simple cycle in a graph is an Eulerian subgraph, but there may be others. The cycle space of a graph is the collection of its Eulerian subgraphs. It forms a vector space over the two-element finite field. The vector addition operation is the symmetric difference of two or more subgraphs, which forms another subgraph consisting of the edges that appear an odd number of times in the arguments to the symmetric difference operation. [1]

A cycle basis is a basis of this vector space in which each basis vector represents a simple cycle. It consists of a set of cycles that can be combined, using symmetric differences, to form every Eulerian subgraph, and that is minimal with this property. Every cycle basis of a given graph has the same number of cycles, which equals the dimension of its cycle space. This number is called the circuit rank of the graph, and it equals where is the number of edges in the graph, is the number of vertices, and is the number of connected components. [2]

Special cycle bases

Several special types of cycle bases have been studied, including the fundamental cycle bases, weakly fundamental cycle bases, sparse (or 2-) cycle bases, and integral cycle bases. [3]

Induced cycles

Every graph has a cycle basis in which every cycle is an induced cycle. In a 3-vertex-connected graph, there always exists a basis consisting of peripheral cycles, cycles whose removal does not separate the remaining graph. [4] [5] In any graph other than one formed by adding one edge to a cycle, a peripheral cycle must be an induced cycle.

Fundamental cycles

If is a spanning tree or spanning forest of a given graph , and is an edge that does not belong to , then the fundamental cycle defined by is the simple cycle consisting of together with the path in connecting the endpoints of . There are exactly fundamental cycles, one for each edge that does not belong to . Each of them is linearly independent from the remaining cycles, because it includes an edge that is not present in any other fundamental cycle. Therefore, the fundamental cycles form a basis for the cycle space. [1] [2] A cycle basis constructed in this way is called a fundamental cycle basis or strongly fundamental cycle basis. [3]

It is also possible to characterize fundamental cycle bases without specifying the tree for which they are fundamental. There exists a tree for which a given cycle basis is fundamental if and only if each cycle contains an edge that is not included in any other basis cycle, that is, each cycle is independent of others. It follows that a collection of cycles is a fundamental cycle basis of if and only if it has the independence property and has the correct number of cycles to be a basis of . [6]

Weakly fundamental cycles

A cycle basis is called weakly fundamental if its cycles can be placed into a linear ordering such that each cycle includes at least one edge that is not included in any earlier cycle. A fundamental cycle basis is automatically weakly fundamental (for any edge ordering). [3] [7] If every cycle basis of a graph is weakly fundamental, the same is true for every minor of the graph. Based on this property, the class of graphs (and multigraphs) for which every cycle basis is weakly fundamental can be characterized by five forbidden minors: the graph of the square pyramid, the multigraph formed by doubling all edges of a four-vertex cycle, two multigraphs formed by doubling two edges of a tetrahedron, and the multigraph formed by tripling the edges of a triangle. [8]

Face cycles

If a connected finite planar graph is embedded into the plane, each face of the embedding is bounded by a cycle of edges. One face is necessarily unbounded (it includes points arbitrarily far from the vertices of the graph) and the remaining faces are bounded. By Euler's formula for planar graphs, there are exactly bounded faces. The symmetric difference of any set of face cycles is the boundary of the corresponding set of faces, and different sets of bounded faces have different boundaries, so it is not possible to represent the same set as a symmetric difference of face cycles in more than one way; this means that the set of face cycles is linearly independent. As a linearly independent set of enough cycles, it necessarily forms a cycle basis. [9] It is always a weakly fundamental cycle basis, and is fundamental if and only if the embedding of the graph is outerplanar.

For graphs properly embedded onto other surfaces so that all faces of the embedding are topological disks, it is not in general true that there exists a cycle basis using only face cycles. The face cycles of these embeddings generate a proper subset of all Eulerian subgraphs. The homology group of the given surface characterizes the Eulerian subgraphs that cannot be represented as the boundary of a set of faces. Mac Lane's planarity criterion uses this idea to characterize the planar graphs in terms of the cycle bases: a finite undirected graph is planar if and only if it has a sparse cycle basis or 2-basis, [3] a basis in which each edge of the graph participates in at most two basis cycles. In a planar graph, the cycle basis formed by the set of bounded faces is necessarily sparse, and conversely, a sparse cycle basis of any graph necessarily forms the set of bounded faces of a planar embedding of its graph. [9] [10]

Integral bases

The cycle space of a graph may be interpreted using the theory of homology as the homology group of a simplicial complex with a point for each vertex of the graph and a line segment for each edge of the graph. This construction may be generalized to the homology group over an arbitrary ring . An important special case is the ring of integers, for which the homology group is a free abelian group, a subgroup of the free abelian group generated by the edges of the graph. Less abstractly, this group can be constructed by assigning an arbitrary orientation to the edges of the given graph; then the elements of are labelings of the edges of the graph by integers with the property that, at each vertex, the sum of the incoming edge labels equals the sum of the outgoing edge labels. The group operation is addition of these vectors of labels. An integral cycle basis is a set of simple cycles that generates this group. [3]

Minimum weight

If the edges of a graph are given real number weights, the weight of a subgraph may be computed as the sum of the weights of its edges. The minimum weight basis of the cycle space is necessarily a cycle basis: by Veblen's theorem, [11] every Eulerian subgraph that is not itself a simple cycle can be decomposed into multiple simple cycles, which necessarily have smaller weight.

By standard properties of bases in vector spaces and matroids, the minimum weight cycle basis not only minimizes the sum of the weights of its cycles, it also minimizes any other monotonic combination of the cycle weights. For instance, it is the cycle basis that minimizes the weight of its longest cycle. [12]

Polynomial time algorithms

In any vector space, and more generally in any matroid, a minimum weight basis may be found by a greedy algorithm that considers potential basis elements one at a time, in sorted order by their weights, and that includes an element in the basis when it is linearly independent of the previously chosen basis elements. Testing for linear independence can be done by Gaussian elimination. However, an undirected graph may have an exponentially large set of simple cycles, so it would be computationally infeasible to generate and test all such cycles.

Horton (1987) provided the first polynomial time algorithm for finding a minimum weight basis, in graphs for which every edge weight is positive. His algorithm uses this generate-and-test approach, but restricts the generated cycles to a small set of cycles, called Horton cycles. A Horton cycle is a fundamental cycle of a shortest path tree of the given graph. There are at most n different shortest path trees (one for each starting vertex) and each has fewer than m fundamental cycles, giving the bound on the total number of Horton cycles. As Horton showed, every cycle in the minimum weight cycle basis is a Horton cycle. [13] Using Dijkstra's algorithm to find each shortest path tree and then using Gaussian elimination to perform the testing steps of the greedy basis algorithm leads to a polynomial time algorithm for the minimum weight cycle basis. Subsequent researchers have developed improved algorithms for this problem, [14] [15] [16] [17] reducing the worst-case time complexity for finding a minimum weight cycle basis in a graph with edges and vertices to . [18]

NP-hardness

Finding the fundamental basis with the minimum possible weight is closely related to the problem of finding a spanning tree that minimizes the average of the pairwise distances; both are NP-hard. [19] Finding a minimum weight weakly fundamental basis is also NP-hard, [7] and approximating it is MAXSNP-hard. [20] If negative weights and negatively weighted cycles are allowed, then finding a minimum cycle basis (without restriction) is also NP-hard, as it can be used to find a Hamiltonian cycle: if a graph is Hamiltonian, and all edges are given weight −1, then a minimum weight cycle basis necessarily includes at least one Hamiltonian cycle.

In planar graphs

The minimum weight cycle basis for a planar graph is not necessarily the same as the basis formed by its bounded faces: it can include cycles that are not faces, and some faces may not be included as cycles in the minimum weight cycle basis. However, there exists a minimum weight cycle basis in which no two cycles cross each other: for every two cycles in the basis, either the cycles enclose disjoint subsets of the bounded faces, or one of the two cycles encloses the other one. This set of cycles corresponds, in the dual graph of the given planar graph, to a set of cuts that form a Gomory–Hu tree of the dual graph, the minimum weight basis of its cut space. [21] Based on this duality, an implicit representation of the minimum weight cycle basis in a planar graph can be constructed in time . [22]

Applications

Cycle bases have been used for solving periodic scheduling problems, such as the problem of determining the schedule for a public transportation system. In this application, the cycles of a cycle basis correspond to variables in an integer program for solving the problem. [23]

In the theory of structural rigidity and kinematics, cycle bases are used to guide the process of setting up a system of non-redundant equations that can be solved to predict the rigidity or motion of a structure. In this application, minimum or near-minimum weight cycle bases lead to simpler systems of equations. [24]

In distributed computing, cycle bases have been used to analyze the number of steps needed for an algorithm to stabilize. [25]

In bioinformatics, cycle bases have been used to determine haplotype information from genome sequence data. [26] Cycle bases have also been used to analyze the tertiary structure of RNA. [27]

The minimum weight cycle basis of a nearest neighbor graph of points sampled from a three-dimensional surface can be used to obtain a reconstruction of the surface. [28]

In cheminformatics, the minimal cycle basis of a molecular graph is referred to as the smallest set of smallest rings. [29] [30] [31]

Related Research Articles

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

<span class="mw-page-title-main">Minimum spanning tree</span> Least-weight tree connecting graph vertices

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.

<span class="mw-page-title-main">Hamiltonian path</span> Path in a graph that visits each vertex exactly once

In the mathematical field of graph theory, a Hamiltonian path is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. The computational problems of determining whether such paths and cycles exist in graphs are NP-complete.

In graph theory, a branch of mathematics, the (binary) cycle space of an undirected graph is the set of its even-degree subgraphs.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

<span class="mw-page-title-main">Spanning tree</span> Tree which includes all vertices of a graph

In the mathematical field of graph theory, a spanning treeT of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree. If all of the edges of G are also edges of a spanning tree T of G, then G is a tree and is identical to T.

<span class="mw-page-title-main">Chordal graph</span> Graph where all long cycles have a chord

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs.

In the mathematical theory of matroids, a graphic matroid is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called co-graphic matroids or bond matroids. A matroid that is both graphic and co-graphic is sometimes called a planar matroid ; these are exactly the graphic matroids formed from planar graphs.

<span class="mw-page-title-main">Circuit rank</span> Fewest graph edges whose removal breaks all cycles

In graph theory, a branch of mathematics, the circuit rank, cyclomatic number, cycle rank, or nullity of an undirected graph is the minimum number of edges that must be removed from the graph to break all its cycles, making it into a tree or forest. It is equal to the number of independent cycles in the graph. Unlike the corresponding feedback arc set problem for directed graphs, the circuit rank r is easily computed using the formula

<span class="mw-page-title-main">Feedback arc set</span> Edges that hit all cycles in a graph

In graph theory and graph algorithms, a feedback arc set or feedback edge set in a directed graph is a subset of the edges of the graph that contains at least one edge out of every cycle in the graph. Removing these edges from the graph breaks all of the cycles, producing an acyclic subgraph of the given graph, often called a directed acyclic graph. A feedback arc set with the fewest possible edges is a minimum feedback arc set and its removal leaves a maximum acyclic subgraph; weighted versions of these optimization problems are also used. If a feedback arc set is minimal, meaning that removing any edge from it produces a subset that is not a feedback arc set, then it has an additional property: reversing all of its edges, rather than removing them, produces a directed acyclic graph.

The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph. The Nash-Williams theorem provides necessary and sufficient conditions for when a graph is k-arboric.

<span class="mw-page-title-main">Dual graph</span> Graph representing faces of another graph

In the mathematical discipline of graph theory, the dual graph of a planar graph G is a graph that has a vertex for each face of G. The dual graph has an edge for each pair of faces in G that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge e of G has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of e. The definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

<span class="mw-page-title-main">Book embedding</span> Graph layout on multiple half-planes

In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings in a book, a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on this boundary line, called the spine, and the edges are required to stay within a single half-plane. The book thickness of a graph is the smallest possible number of half-planes for any book embedding of the graph. Book thickness is also called pagenumber, stacknumber or fixed outerthickness. Book embeddings have also been used to define several other graph invariants including the pagewidth and book crossing number.

<span class="mw-page-title-main">Cactus graph</span> Mathematical tree of cycles

In graph theory, a cactus is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple cycle, or in which every block is an edge or a cycle.

<span class="mw-page-title-main">Peripheral cycle</span> Graph cycle which does not separate remaining elements

In graph theory, a peripheral cycle in an undirected graph is, intuitively, a cycle that does not separate any part of the graph from any other part. Peripheral cycles were first studied by Tutte (1963), and play important roles in the characterization of planar graphs and in generating the cycle spaces of nonplanar graphs.

In graph theory, the planarity testing problem is the algorithmic problem of testing whether a given graph is a planar graph (that is, whether it can be drawn in the plane without edge intersections). This is a well-studied problem in computer science for which many practical algorithms have emerged, many taking advantage of novel data structures. Most of these methods operate in O(n) time (linear time), where n is the number of edges (or vertices) in the graph, which is asymptotically optimal. Rather than just being a single Boolean value, the output of a planarity testing algorithm may be a planar graph embedding, if the graph is planar, or an obstacle to planarity such as a Kuratowski subgraph if it is not.

In graph theory, the planar separator theorem is a form of isoperimetric inequality for planar graphs, that states that any planar graph can be split into smaller pieces by removing a small number of vertices. Specifically, the removal of vertices from an n-vertex graph can partition the graph into disjoint subgraphs each of which has at most vertices.

<span class="mw-page-title-main">Halin graph</span> Mathematical tree with cycle through leaves

In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none of its edges cross, and the cycle connects the leaves in their clockwise ordering in this embedding. Thus, the cycle forms the outer face of the Halin graph, with the tree inside it.

In theoretical computer science, Baker's technique is a method for designing polynomial-time approximation schemes (PTASs) for problems on planar graphs. It is named after Brenda Baker, who announced it in a 1983 conference and published it in the Journal of the ACM in 1994.

<span class="mw-page-title-main">Matroid parity problem</span> Largest independent set of paired elements

In combinatorial optimization, the matroid parity problem is a problem of finding the largest independent set of paired elements in a matroid. The problem was formulated by Lawler (1976) as a common generalization of graph matching and matroid intersection. It is also known as polymatroid matching, or the matchoid problem.

References

  1. 1 2 Diestel, Reinhard (2012), "1.9 Some linear algebra", Graph Theory, Graduate Texts in Mathematics, vol. 173, Springer, pp. 23–28.
  2. 1 2 Gross, Jonathan L.; Yellen, Jay (2005), "4.6 Graphs and Vector Spaces", Graph Theory and Its Applications (2nd ed.), CRC Press, pp. 197–207, ISBN   9781584885054 .
  3. 1 2 3 4 5 Liebchen, Christian; Rizzi, Romeo (2007), "Classes of cycle bases", Discrete Applied Mathematics, 155 (3): 337–355, doi: 10.1016/j.dam.2006.06.007 , MR   2303157 .
  4. ↑ Diestel (2012), pp. 32, 65.
  5. ↑ Tutte, W. T. (1963), "How to draw a graph", Proceedings of the London Mathematical Society, Third Series, 13: 743–767, doi:10.1112/plms/s3-13.1.743, MR   0158387 . See in particular Theorem 2.5.
  6. ↑ Cribb, D. W.; Ringeisen, R. D.; Shier, D. R. (1981), "On cycle bases of a graph", Proceedings of the Twelfth Southeastern Conference on Combinatorics, Graph Theory and Computing, Vol. I (Baton Rouge, La., 1981), Congressus Numerantium, vol. 32, pp. 221–229, MR   0681883 .
  7. 1 2 Rizzi, Romeo (2009), "Minimum weakly fundamental cycle bases are hard to find", Algorithmica , 53 (3): 402–424, doi:10.1007/s00453-007-9112-8, MR   2482112, S2CID   12675654 .
  8. ↑ Hartvigsen, David; Zemel, Eitan (1989), "Is every cycle basis fundamental?", Journal of Graph Theory , 13 (1): 117–137, doi:10.1002/jgt.3190130115, MR   0982873 .
  9. 1 2 Diestel (2012), pp. 105–106.
  10. ↑ Mac Lane, S. (1937), "A combinatorial condition for planar graphs" (PDF), Fundamenta Mathematicae , 28: 22–32, doi: 10.4064/fm-28-1-22-32 .
  11. ↑ Veblen, Oswald (1912), "An application of modular equations in analysis situs", Annals of Mathematics , Second Series, 14 (1): 86–94, doi:10.2307/1967604, JSTOR   1967604 .
  12. ↑ Chickering, David M.; Geiger, Dan; Heckerman, David (1995), "On finding a cycle basis with a shortest maximal cycle", Information Processing Letters, 54 (1): 55–58, CiteSeerX   10.1.1.650.8218 , doi:10.1016/0020-0190(94)00231-M, MR   1332422 .
  13. ↑ Horton, J. D. (1987), "A polynomial-time algorithm to find the shortest cycle basis of a graph", SIAM Journal on Computing , 16 (2): 358–366, doi:10.1137/0216026 .
  14. ↑ Berger, Franziska; Gritzmann, Peter; de Vries, Sven (2004), "Minimum cycle bases for network graphs", Algorithmica, 40 (1): 51–62, doi:10.1007/s00453-004-1098-x, MR   2071255, S2CID   9386078 .
  15. ↑ Mehlhorn, Kurt; Michail, Dimitrios (2006), "Implementing minimum cycle basis algorithms", ACM Journal of Experimental Algorithmics, 11: 2.5, doi:10.1145/1187436.1216582, S2CID   6198296 .
  16. ↑ Kavitha, Telikepalli; Mehlhorn, Kurt; Michail, Dimitrios; Paluch, Katarzyna E. (2008), "An algorithm for minimum cycle basis of graphs", Algorithmica , 52 (3): 333–349, doi: 10.1007/s00453-007-9064-z , MR   2452919 .
  17. ↑ Kavitha, Telikepalli; Liebchen, Christian; Mehlhorn, Kurt; Michail, Dimitrios; Rizzi, Romeo; Ueckerdt, Torsten; Zweig, Katharina A. (2009), "Cycle bases in graphs: Characterization, algorithms, complexity, and applications", Computer Science Review, 3 (4): 199–243, doi:10.1016/j.cosrev.2009.08.001 .
  18. ↑ Amaldi, Edoardo; Iuliano, Claudio; Rizzi, Romeo (2010), "Efficient deterministic algorithms for finding a minimum cycle basis in undirected graphs", Integer Programming and Combinatorial Optimization: 14th International Conference, IPCO 2010, Lausanne, Switzerland, June 9-11, 2010, Proceedings, Lecture Notes in Computer Science, vol. 6080, Springer, pp. 397–410, Bibcode:2010LNCS.6080..397A, doi:10.1007/978-3-642-13036-6_30, ISBN   978-3-642-13035-9, MR   2661113 .
  19. ↑ Deo, Narsingh; Prabhu, G. M.; Krishnamoorthy, M. S. (1982), "Algorithms for generating fundamental cycles in a graph", ACM Transactions on Mathematical Software , 8 (1): 26–42, doi: 10.1145/355984.355988 , MR   0661120, S2CID   2260051 .
  20. ↑ Galbiati, Giulia; Amaldi, Edoardo (2004), "On the approximability of the minimum fundamental cycle basis problem", Approximation and Online Algorithms: First International Workshop, WAOA 2003, Budapest, Hungary, September 16-18, 2003, Revised Papers, Lecture Notes in Computer Science, vol. 2909, Berlin: Springer, pp. 151–164, doi:10.1007/978-3-540-24592-6_12, ISBN   978-3-540-21079-5, MR   2089904 .
  21. ↑ Hartvigsen, David; Mardon, Russell (1994), "The all-pairs min cut problem and the minimum cycle basis problem on planar graphs", SIAM Journal on Discrete Mathematics , 7 (3): 403–418, doi:10.1137/S0895480190177042, MR   1285579 .
  22. ↑ Borradaile, Glencora; Eppstein, David; Nayyeri, Amir; Wulff-Nilsen, Christian (2016), "All-pairs minimum cuts in near-linear time for surface-embedded graphs", Proc. 32nd Int. Symp. Computational Geometry, Leibniz International Proceedings in Informatics (LIPIcs), vol. 51, Schloss Dagstuhl, pp. 22:1–22:16, arXiv: 1411.7055 , doi:10.4230/LIPIcs.SoCG.2016.22, S2CID   215762172 .
  23. ↑ Liebchen, Christian (2007), "Periodic Timetable Optimization in Public Transport", Operations Research Proceedings 2006, vol. 2006, pp. 29–36, doi:10.1007/978-3-540-69995-8_5, ISBN   978-3-540-69994-1 .
  24. ↑ Cassell, A. C.; De Henderson, J. C.; Kaveh, A. (1974), "Cycle bases for the flexibility analysis of structures", International Journal for Numerical Methods in Engineering, 8 (3): 521–528, Bibcode:1974IJNME...8..521C, doi:10.1002/nme.1620080308 .
  25. ↑ Boulinier, Christian; Petit, Franck; Villain, Vincent (2004), "When graph theory helps self-stabilization", Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing (PODC '04), New York, NY, USA: ACM, pp. 150–159, CiteSeerX   10.1.1.79.2190 , doi:10.1145/1011767.1011790, ISBN   978-1581138023, S2CID   14936510 .
  26. ↑ Aguiar, Derek; Istrail, Sorin (2012), "HapCompass: A Fast Cycle Basis Algorithm for Accurate Haplotype Assembly of Sequence Data", Journal of Computational Biology, 19 (6): 577–590, doi:10.1089/cmb.2012.0084, PMC   3375639 , PMID   22697235 .
  27. ↑ Lemieux, Sébastien; Major, François (2006), "Automated extraction and classification of RNA tertiary structure cyclic motifs", Nucleic Acids Research, 34 (8): 2340–2346, doi:10.1093/nar/gkl120, PMC   1458283 , PMID   16679452 .
  28. ↑ Gotsman, Craig; Kaligosi, Kanela; Mehlhorn, Kurt; Michail, Dimitrios; Pyrga, Evangelia (2007), "Cycle bases of graphs and sampled manifolds", Computer Aided Geometric Design, 24 (8–9): 464–480, CiteSeerX   10.1.1.298.9661 , doi:10.1016/j.cagd.2006.07.001, MR   2359763 .
  29. ↑ May, John W.; Steinbeck, Christoph (2014), "Efficient ring perception for the Chemistry Development Kit", Journal of Cheminformatics , 6 (3): 3, doi: 10.1186/1758-2946-6-3 , PMC   3922685 , PMID   24479757
  30. ↑ Downs, G.M.; Gillet, V.J.; Holliday, J.D.; Lynch, M.F. (1989), "A review of ring perception algorithms for chemical graphs", J. Chem. Inf. Comput. Sci. , 29 (3): 172–187, doi:10.1021/ci00063a007
  31. ↑ Zamora, A. (1979), "An algorithm for finding the smallest set of smallest rings", J. Chem. Inf. Comput. Sci. , 16 (1): 40–43, doi:10.1021/ci60005a013
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.