@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 = "Funding Information: The research of this author was supported by NSF grant NSF-DCR-8318874 and ONR grant N00014-85-K-0046. The research of these authors was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U. S. Department of Energy under contract number DE-AC02-76ER03077. Funding Information: 2. The research of this author was supported by NSF grant NSF-DCR-8318874 and ONR grant N00014-85-K-0046. 3. The research of these authors was supported by the Applied Mathematical Sciences subprogram of the Office of Energy Research, U. S. Department of Energy under contract number DE-AC02-76ER03077. 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",

}