Parallel ear decomposition search (EDS) and st-numbering in graphs

Yael Maon, Baruch Schieber, Uzi Vishkin

Research output: Contribution to journalArticlepeer-review

79 Scopus citations

Abstract

The linear time serial algorithm of Lempel et al. (1967) for testing planarity of graphs uses the linear time serial algorithm of Even and Tarjan (1976) for st-numbering. This st-numbering algorithm is based on depth-first search (DFS). A known conjecture states that DFS, which is a key technique in designing serial algorithms, is not amenable to poly-log time parallelism using 'around linearly' (or even polynomially) many processors. The first contribution of this paper is a general method for searching efficiently in parallel undirected graphs, called ear decomposition search (EDS). The second contribution demonstrates the applicability of this search method. We present an efficient parallel algorithm for st-numbering in a biconnected graph. The algorithm runs in logarithmic time using a linear number of processors on a concurrent-read concurrent-write (CRCW) PRAM. An efficient parallel algorithm for the problem did not exist before. The problem was not even known to be in NC.

Original languageEnglish (US)
Pages (from-to)277-298
Number of pages22
JournalTheoretical Computer Science
Volume47
Issue numberC
DOIs
StatePublished - 1986
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Parallel ear decomposition search (EDS) and st-numbering in graphs'. Together they form a unique fingerprint.

Cite this