Thumbnail
Access Restriction
Subscribed

Author Paton, Keith
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Graph ♦ Spanning tree ♦ Algorithm ♦ Cycle ♦ Fundamental cycle set
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.
Description Affiliation: Medical Research Council, London, England (Paton, Keith)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 12
Issue Number 9
Page Count 5
Starting Page 514
Ending Page 518


Open content in new tab

   Open content in new tab
Source: ACM Digital Library