Finding biconnected componemts and computing tree functions in logarithmic parallel time

Robert E. Tarjan, Uzi Vishkin

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

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.

Original languageEnglish (US)
Title of host publication25th Annual Symposium on Foundations of Computer Science, FOCS 1984
PublisherIEEE Computer Society
Pages12-20
Number of pages9
ISBN (Electronic)081860591X
StatePublished - 1984
Externally publishedYes
Event25th Annual Symposium on Foundations of Computer Science, FOCS 1984 - Singer Island, United States
Duration: Oct 24 1984Oct 26 1984

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume1984-October
ISSN (Print)0272-5428

Conference

Conference25th Annual Symposium on Foundations of Computer Science, FOCS 1984
Country/TerritoryUnited States
CitySinger Island
Period10/24/8410/26/84

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Biconnected components
  • Blocks
  • Parallel graph algorithm
  • Spanning tree

Fingerprint

Dive into the research topics of 'Finding biconnected componemts and computing tree functions in logarithmic parallel time'. Together they form a unique fingerprint.

Cite this