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 Citations (Scopus)

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 - Jan 1 1986
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

Conference

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

Fingerprint

Decomposition
Parallel algorithms
Testing

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Maon, Y., Schieber, B., & Vishkin, U. (1986). Parallel ear decomposition search (Eds) and st-numbering in graphs. In K. Mehlhorn, F. Makedon, T. Papatheodorou, & P. Spirakis (Eds.), VLSl Algorithms and Architectures - Aegean Workshop on Computing, Proceedings (pp. 34-45). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 227 LNCS). Springer Verlag. https://doi.org/10.1007/3-540-16766-8_4
Maon, Yael ; Schieber, Baruch ; Vishkin, Uzi. / Parallel ear decomposition search (Eds) and st-numbering in graphs. VLSl Algorithms and Architectures - Aegean Workshop on Computing, Proceedings. editor / Kurt Mehlhorn ; Fillia Makedon ; T. Papatheodorou ; P. Spirakis. Springer Verlag, 1986. pp. 34-45 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{6cc0c1cccb884dd0803b236770613221,
title = "Parallel ear decomposition search (Eds) and st-numbering in graphs",
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.",
author = "Yael Maon and Baruch Schieber and Uzi Vishkin",
year = "1986",
month = "1",
day = "1",
doi = "https://doi.org/10.1007/3-540-16766-8_4",
language = "English (US)",
isbn = "9783540167662",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "34--45",
editor = "Kurt Mehlhorn and Fillia Makedon and T. Papatheodorou and P. Spirakis",
booktitle = "VLSl Algorithms and Architectures - Aegean Workshop on Computing, Proceedings",
address = "Germany",

}

Maon, Y, Schieber, B & Vishkin, U 1986, Parallel ear decomposition search (Eds) and st-numbering in graphs. in K Mehlhorn, F Makedon, T Papatheodorou & P Spirakis (eds), VLSl Algorithms and Architectures - Aegean Workshop on Computing, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 227 LNCS, Springer Verlag, pp. 34-45, Aegean Workshop on Computing: VLSI Algorithms and Architectures, AWOC 1986, Loutrak, Greece, 7/8/86. https://doi.org/10.1007/3-540-16766-8_4

Parallel ear decomposition search (Eds) and st-numbering in graphs. / Maon, Yael; Schieber, Baruch; Vishkin, Uzi.

VLSl Algorithms and Architectures - Aegean Workshop on Computing, Proceedings. ed. / Kurt Mehlhorn; Fillia Makedon; T. Papatheodorou; P. Spirakis. Springer Verlag, 1986. p. 34-45 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 227 LNCS).

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

TY - GEN

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

AU - Maon, Yael

AU - Schieber, Baruch

AU - Vishkin, Uzi

PY - 1986/1/1

Y1 - 1986/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85025286042&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85025286042&partnerID=8YFLogxK

U2 - https://doi.org/10.1007/3-540-16766-8_4

DO - https://doi.org/10.1007/3-540-16766-8_4

M3 - Conference contribution

SN - 9783540167662

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 34

EP - 45

BT - VLSl Algorithms and Architectures - Aegean Workshop on Computing, Proceedings

A2 - Mehlhorn, Kurt

A2 - Makedon, Fillia

A2 - Papatheodorou, T.

A2 - Spirakis, P.

PB - Springer Verlag

ER -

Maon Y, Schieber B, Vishkin U. Parallel ear decomposition search (Eds) and st-numbering in graphs. In Mehlhorn K, Makedon F, Papatheodorou T, Spirakis P, editors, VLSl Algorithms and Architectures - Aegean Workshop on Computing, Proceedings. Springer Verlag. 1986. p. 34-45. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-16766-8_4