Keith Paton
Abstract
A fast method is presented for finding a fundamental set of cycles for an undirected finite graph. A spanning tree is grown and the vertices examined in turn, unexamined vertices being stored in a pushdown list to await examination. One stage in the process is to take the top element v of the pushdown list and examine it, i.e. inspect all those edges (v, z) of the graph for which z has not yet been examined. If z is already in the tree, a fundamental cycle is added; if not, the edge (v, z) is placed in the tree. There is exactly one such stage for each of the n vertices of the graph. For large n, the store required increases as n2 and the time as nγ where γ depends on the type of graph involved. γ is bounded below by 2 and above by 3, and it is shown that both bounds are attained.
In terms of storage our algorithm is similar to that of Gotlieb and Corneil and superior to that of Welch; in terms of speed it is similar to that of Welch and superior to that of Gotlieb and Corneil. Tests show our algorithm to be remarkably efficient (γ = 2) on random graphs.
- 1 GOULD, R. The application of graph theory to the synthesis of contact networks. Proc. International Symp. on the Theory of Switching, Pt. I, Apr. 2-5, 1957. In The Annals of the Computation Laboratory of Harvard University, Annals No. 29, Harvard U. Press, Cambridge, Mass., 1959, pp. 244-292.Google Scholar
- 2 WELCH, J. T., JR. A mechanical analysis of the cyclic structure of undirected linear graphs. J. ACM 18, 2 (Apr. 1966), 205-210. Google ScholarDigital Library
- 3 GOTLIEB, C. C., AND CORNEIL, D.G. Algorithms for finding a fundamental set of cycles for an undirected linear graph. Comm. ACM 10, 12 (Dec. 1967), 780-783. Google ScholarDigital Library
- 4 SUSSENGUTH, E., JR. A graph theoretical algorithm for matching chemical structures. J. Chem. Doe. 5, 1 (Feb. 1965), 36-43.Google ScholarCross Ref
Index Terms
- An algorithm for finding a fundamental set of cycles of a graph
Recommendations
An algorithm for the blocks and cutnodes of a graph
An efficient method is presented for finding blocks and cutnodes of an arbitrary undirected graph. The graph may be represented either (i) as an ordered list of edges or (ii) as a packed adjacency matrix. If w denotes the word length of the machine ...
Acyclic 5-choosability of planar graphs with neither 4-cycles nor chordal 6-cycles
A proper vertex coloring of a graph G=(V,E) is acyclic if G contains no bicolored cycle. A graph G is acyclically L-list colorable if for a given list assignment L={L(v):v@?V}, there exists a proper acyclic coloring @f of G such that @f(v)@?L(v) for all ...
Equitable colorings of planar graphs without short cycles
An equitable coloring of a graph is a proper vertex coloring such that the sizes of every two color classes differ by at most 1. Chen, Lih, and Wu conjectured that every connected graph G with maximum degree @D>=2 has an equitable coloring with @D ...
Comments