TY - JOUR
T1 - Parallel ear decomposition search (EDS) and st-numbering in graphs
AU - Maon, Yael
AU - Schieber, Baruch
AU - Vishkin, Uzi
N1 - Funding Information:
* 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. ** The research of this author was supported by NSF Grant NSF-DCR-8318874 and ONR Grant N00014-85-K-0046.
PY - 1986
Y1 - 1986
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0023005121&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0023005121&partnerID=8YFLogxK
U2 - 10.1016/0304-3975(86)90153-2
DO - 10.1016/0304-3975(86)90153-2
M3 - Article
AN - SCOPUS:0023005121
SN - 0304-3975
VL - 47
SP - 277
EP - 298
JO - Theoretical Computer Science
JF - Theoretical Computer Science
IS - C
ER -