TY - JOUR
T1 - Planar strong connectivity helps in parallel depth-first search
AU - Kao, Ming Yang
PY - 1995
Y1 - 1995
N2 - This paper proves that for a strongly connected planar directed graph of size n, a depth-first search tree rooted at a specified vertex can be computed in O(log5 n) time with n/log n processors. Previously, for planar directed graphs that may not be strongly connected, the best depth-first search algorithm runs in O(log10 n) time with n processors. Both algorithms run on a parallel random access machine that allows concurrent reads and concurrent writes in its shared memory, and in case of a write conflict, permits an arbitrary processor to succeed.
AB - This paper proves that for a strongly connected planar directed graph of size n, a depth-first search tree rooted at a specified vertex can be computed in O(log5 n) time with n/log n processors. Previously, for planar directed graphs that may not be strongly connected, the best depth-first search algorithm runs in O(log10 n) time with n processors. Both algorithms run on a parallel random access machine that allows concurrent reads and concurrent writes in its shared memory, and in case of a write conflict, permits an arbitrary processor to succeed.
UR - http://www.scopus.com/inward/record.url?scp=0029246659&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0029246659&partnerID=8YFLogxK
U2 - 10.1137/S0097539792227077
DO - 10.1137/S0097539792227077
M3 - Article
AN - SCOPUS:0029246659
SN - 0097-5397
VL - 24
SP - 46
EP - 62
JO - SIAM Journal on Computing
JF - SIAM Journal on Computing
IS - 1
ER -