DIMACS TR: 94-29
An NC algorithm for depth-first search of graphs of bounded genus
Authors: Justin R. Smith and Olga Rayskina
ABSTRACT
In this paper we develop a deterministic NC algorithm for performing
a depth-first search on an undirected graph embedded in a surface of
bounded genus. The algorithm runs on a SIMD P-RAM computer like the
Connection Machine. The problem of depth-first search of graphs is
interesting for a number of reasons. Many well-known sequential
algorithms are based upon performing a depth-first search of a graph
and the difficulty in finding a parallel algorithm for depth-first
search is a fundamental obstacle to parallelizing the other
algorithms. In addition, it has been proved that the problem of
finding a lexicographically-first depth-first search of a graph is
P-complete. Part I of this paper, (Justin Smith, ``Parallel
algorithms for depth-first searches I. The planar case'', SIAM J.
Comput., vol. 15, no. 3, pp. 814--830, 1986), developed such an
algorithm for a depth-first search on a planar graph. The algorithm
presented there has been extended and generalized by a number of
people. Aggarwal and Anderson developed a Random NC algorithm for
depth-first search on general graphs in (Alok Aggarwal and Richard
Anderson, ``A random NC algorithm for depth-first-search'', in
Symposium on the Theory of Computing. 1987, vol. 19, pp. 325--334,
ACM) and Shannon improved upon the execution time and number of
processors required to perform depth-first search on a planar graph in
(Gregory Shannon, ``A linear-processor algorithm for depth-first
search in planar graphs'', Inform. Process. Lett., vol. 29, no. 3,
pp. 119--124, 1988). Our algorithm executes in O((g + 1)lg n)-time,
using O(n^2) processors.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1994/94-29.ps
DIMACS Home Page