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

Yael Maon, Baruch Schieber, Uzi Vishkin

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

8 Scopus citations

Abstract

The linear time serial algorithm for planarity testing of [LEC-67] uses the linear time serial algorithm of [ET-76] 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 is quite subtle and 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. It was not even known to be in NC.

Original languageEnglish (US)
Title of host publicationVLSl Algorithms and Architectures - Aegean Workshop on Computing, Proceedings
EditorsKurt Mehlhorn, Fillia Makedon, T. Papatheodorou, P. Spirakis
PublisherSpringer Verlag
Pages34-45
Number of pages12
ISBN (Print)9783540167662
DOIs
StatePublished - 1986
Externally publishedYes
EventAegean Workshop on Computing: VLSI Algorithms and Architectures, AWOC 1986 - Loutrak, Greece
Duration: Jul 8 1986Jul 11 1986

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume227 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceAegean Workshop on Computing: VLSI Algorithms and Architectures, AWOC 1986
CountryGreece
CityLoutrak
Period7/8/867/11/86

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