×

A random NC algorithm for depth first search. (English) Zbl 0647.68060

We present a fast parallel algorithm for constructing a depth first search tree for an undirected graph. The algorithms is an RNC algorithm, meaning that it is a probabilistic algorithm that runs in polylog time using a polynomial number of processors on a P-RAM. The run time of the algorithm is \(O(T_{MM}(n)\log^ 3 n)\), and the number of processors used is \(P_{MM}(n)\) where \(T_{MM}n)\) and \(P_{MM}(n)\) are the time and number of processors needed to find a minimum weight perfect matching on an n vertex graph with maximum edge weight n.

MSC:

68P10 Searching and sorting
68Q25 Analysis of algorithms and problem complexity
68R10 Graph theory (including graph drawing) in computer science
05C99 Graph theory
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R. J. Anderson, A parallel algorithm for the maximal path problem,Combinatorica,7 (1987), 315–326. · Zbl 0641.68105 · doi:10.1007/BF02579320
[2] R. J.Anderson, A parallel algorithm for depth-first search,Extended Abstract, Math. Science Research Institute (1986).
[3] R. J.Anderson and E.Mayr, Parallelism and greedy algorithms,Technical Report No. STAN-CS-84-1003,Computer Science Department, Stanford University (1984).
[4] S. A. Cook, A taxonomy of problems with fast parallel algorithms,Information and Control,64 (1985), 2–22. · Zbl 0575.68045 · doi:10.1016/S0019-9958(85)80041-3
[5] D.Eckstein and D.Alton, Parallel graph processing using depth first search,Proc. of the Conf. on Theoretical Computer Science at the Univ. of Waterloo, (1977), 21–29. · Zbl 0408.68060
[6] S. Even andR. E. Tarjan, Network flow and testing graph connectivity,SIAM Journal of Computing,4 (1975), 507–518. · Zbl 0328.90031 · doi:10.1137/0204043
[7] R. K. Ghosh andG. P. Bhattacharjee, A parallel search algorithm for directed acyclic graphs,BIT,24 (1984), 134–150. · Zbl 0542.68049 · doi:10.1007/BF01937481
[8] R. M. Karp, E. Upfal andA. Wigderson, Constructing a maximum matching is in randomNC, Combinatorica,6 (1986), 35–48. · Zbl 0646.05051 · doi:10.1007/BF02579407
[9] R. M. Karp andA. Wigderson, A fast parallel algorithm for the maximal independent set problem,Journal of ACM,32 (1985), 762–773. · Zbl 0633.68026 · doi:10.1145/4221.4226
[10] R. J. Lipton andR. E. Tarjan, A separator theorem for planar graphs,SIAM Journal of Applied Math. 36 (1979), 177–189. · Zbl 0432.05022 · doi:10.1137/0136016
[11] K. Mulmuley, U. V. Vazirani andV. V. Vazirani, Matching is as easy as matrix inversion,Combinatorica 7 (1986), 105–114. · Zbl 0632.68041 · doi:10.1007/BF02579206
[12] V.Ramachandran,Personal Communication.
[13] E. Reghbati andD. Corneil, Parallel computations in graph theory,SIAM Journal of Computing,7 (1978), 230–237. · Zbl 0375.68026 · doi:10.1137/0207020
[14] J. H. Reif, Depth-first search is inherently sequential,Information Processing Letters,20 (1985), 229–234. · Zbl 0572.68051 · doi:10.1016/0020-0190(85)90024-9
[15] J. R. Smith, Parallel algorithms for depth first searches,SIAM Journal of Computing,15 (1986), 814–830. · Zbl 0612.68059 · doi:10.1137/0215058
[16] R. E. Tarjan, Depth-first search and linear graph algorithms,SIAM J. of Computing,1 (1972), 146–160. · Zbl 0251.05107 · doi:10.1137/0201010
[17] J. C.Wyllie,The Complexity of Parallel Computations, Phd. Thesis, Department of Computer Science, Cornell University, 1979.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.