Research and Advances

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 employed, the storage (in machine words) required for a graph with n nodes and m edges increases essentially as 2(m + n) in case (i), or n2/w in case (ii). A spanning tree with labeled edges is grown, two edges finally bearing different labels if and only if they belong to different blocks. For both representations the time required to analyze a graph on n nodes increases as n&ggr; where &ggr; depends on the type of graph, 1 ≤ &ggr; ≤ 2, and both bounds are attained. Values of &ggr; are derived for each of several suitable families of test graphs, generated by an extension of the web grammar approach. The algorithm is compared in detail with that proposed by Read for which 1 ≤ &ggr; ≤ 3.

Advertisement

Author Archives

Research and Advances

An algorithm for finding a fundamental set of cycles of a graph

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&ggr; where &ggr; depends on the type of graph involved. &ggr; 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 (&ggr; = 2) on random graphs.

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved