@inproceedings{1532fee33afb42998f1398811ed36150,

title = "Finding biconnected componemts and computing tree functions in logarithmic parallel time",

abstract = "In this paper we propose a new algorithm for finding the blocks (biconnected components) of an undirected graph. A serial implementation runs in O(n+m) time and space on a graph of n vertices and m edges. 4 parallel implementation runs in O(log n) time and O(n+m) space using O(n+m) processors on a concurrent-read, concurrent-write parallel RAM. An alternative implementation runs in O(n2/p2 time and O(n2) space using any number p < n2 /log2 n of processors, on a concurrent-read, exclusive-write parallel RAM. The latter algorithm has optimal speedup, assuming an adjacency matrix representation of the input. A general algorithmic technique which simplifies and improves computation of various functions on trees is introduced. This technique typically requires o(log n) time using O(n) processors and O(n) space on an exclusive-read exclusive-write parallel RAM. ",

keywords = "Biconnected components, Blocks, Parallel graph algorithm, Spanning tree",

author = "Tarjan, {Robert E.} and Uzi Vishkin",

note = "Funding Information: The research of the second author was supported by DOE grant DE-AC02-76ER03077 and by NSF grant NSF-MCS79-21258. Publisher Copyright: {\textcopyright} 1984 IEEE.; 25th Annual Symposium on Foundations of Computer Science, FOCS 1984 ; Conference date: 24-10-1984 Through 26-10-1984",

year = "1984",

language = "English (US)",

series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

publisher = "IEEE Computer Society",

pages = "12--20",

booktitle = "25th Annual Symposium on Foundations of Computer Science, FOCS 1984",

address = "United States",

}