Parallel depth-first search in general directed graphs

ABSTRACT

A directed cycle separator of an n-vertex directed graph is a simple directed cycle such that when the vertices of the cycle are deleted, the resulting graph has no strongly connected component with more than n/2 vertices. This paper shows that the problem of finding a directed cycle separator is in randomized NC. The paper also proves that computing cycle separators and conducting depth-first search in directed graphs are deterministic NC-equivalent. These two results together yield the first RNC algorithm for depth-first search in directed graphs.

REFERENCES

• AA88: A. Aggarwal and R.J. Anderson. A random NC algorithm for depth first search. Combinatorica, 8:1-12, 1988.
• AHU74: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• And87: Richard Anderson, A parallel algorithm for the maximal path problem, Combinatorica, v.7 n.4, p.315-326, Dec, 1987 [doi>10.1007/BF02579320]
• CW87: D. Coppersmith , S. Winograd, Matrix multiplication via arithmetic progressions, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.1-6, January 1987, New York, New York, United States [doi>10.1145/28395.28396]
• GB84: R.K. Ghosh and G.P. Bhat~acharjee. A parallel search algorithm for directed acyclic graphs. BIT, 24:134-150, 1984.
• GPV88: A. Goldberg, S. Plotkin, and P. Vaidya. Sublinear-time parallel Mgorithms for matching and related problems. In Proceedings of the 29th Annual Symposium on Foundations of Computer Science, pages 174- 185, 1988.
• HY88: Xin He , Yaacov Yesha, A nearly optimal parallel algorithm for constructing depth first spanning trees in planar graphs, SIAM Journal on Computing, v.17 n.3, p.486-491, June 1988 [doi>10.1137/0217028]
• JK88: J. Ja'Ja and S. Kosa.raju. Parallel algorithms for planar graphs and related problems. IEEE Transactions on C~rcults and Systems, March 1988.
• Kao88: M. Kao, All graphs have cycle separators and planar directed depth-first search is in DNC (preliminary version), VLSI Algorithms and Architectures, Springer-Verlag, London, 1988
• MVV87: K. Mulmuley , U. V. Vazirani , V. V. Vazirani, Matching is as easy as matrix inversion, Combinatorica, v.7 n.1, p.105-113, Jan. 1987 [doi>10.1007/BF02579206]
• Rei85: J.II. Reif. Depth-first search is inherently sequential. Information Processing Letters, 20:229-234, June 1985.
• Smi86: Justin R Smith, Parallel algorithms for depth-first searches I. planar graphs, SIAM Journal on Computing, v.15 n.3, p.814-830, August 1986 [doi>10.1137/0215058]
• Tar72: R. Tarja.n. Depth-first search and linear gra.ph tdgorithms. SIAM Journal or, Computing, 1(2):146-160, June 1972.
• Zha86: Y. Zhang. PhD thesis, Drexel University, Philadelphia, Pennsylvania, 1986.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms, Theory