@inproceedings{5238cab274ef46e69a2181cdbcc81a2a,
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",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1986.; Aegean Workshop on Computing: VLSI Algorithms and Architectures, AWOC 1986 ; Conference date: 08-07-1986 Through 11-07-1986",
year = "1986",
doi = "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",
}