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 (n^2)/win 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^G where G depends on the type
of graph, 1 <= G <= 2, and both bounds are attained. 
 Values of G 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 <= G <= 3.

CACM July, 1971

Paton, K.

algorithm, block, block-cutpoint-tree, cutnode, fundamental
cycle set, graph, lobe, lobe decomposition 
graph, separable, spanning tree, web grammar

5.32

CA710705 JB February 3, 1978  8:58 AM

1961	4	2177
2177	4	2177
2763	4	2177
1847	5	2177
2177	5	2177
2177	5	2177
2177	5	2177
2490	5	2177
2177	6	2177