Local reorientation, global order, and planar topology

ABSTRACT

Almost every problem on digraphs requires computing strongly connected components and directed spanning trees in one form or another. It has long been an open problem whether polylog time and linear processors are enough to find the strongly connected components of a digraph and compute directed spanning trees for these components. This paper provides the first non-trivial partial solution to this open problem: For a planar digraph with n vertices, the strongly connected components can be computed in O(log3n) time and O(n) processors. If the graph is strongly connected, a directed spanning tree can be built in O(log2 n) time and O(n) processors. Both algorithms are deterministic and run on a parallel random access machine that allows concurrent reads and concurrent writes in its shared memory.

REFERENCES

• AHU74: A. Aho, J. ttopcroft, and J. Illlman. The Design and Analysis of GoT;~puter Algorithms. Addison- Wesley, t974.
• AV84: Mikhail Atallah , Uzi Vishkin, Finding Euler tours in parallel, Journal of Computer and System Sciences, v.29 n.3, p.330-337, Dec. 1984 [doi>10.1016/0022-0000(84)90003-5]
• BM76: John Adrian Bondy, Graph Theory With Applications, Elsevier Science Ltd, 1976
• 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]
• GM88: Hillel Gazit , Gary L. Miller, An improved parallel algorithm that computes the BFS numbering of a directed graph, Information Processing Letters, v.28 n.2, p.61-65, June 24, 1988 [doi>10.1016/0020-0190(88)90164-0]
• Har69: F. Harary. Graph Theory. Addison-Wesley, 1969.
• Kao88: Ming-Yang Kao, All Graphs have Cycle Separators and Planar Directed Depth-First Search is in DNC, Proceedings of the 3rd Aegean Workshop on Computing: VLSI Algorithms and Architectures, p.53-63, June 28-July 01, 1988
• Kao89: M.Y. Kao. A linea,r-processor NC algorithm for planar strongly connected components.
• KR86: P.N. Klein anti J.lt. Reif. An efficient para.}lel algorithm for planarity. In Proceedings of the 17th Annual Symposium on Foundations of Compt~ter Science, pages 465-477, 1986.
• KR88: Richard M. Karp, A Survey of Parallel Algorithms for Shared-Memory Machines, University of California at Berkeley, Berkeley, CA, 1988
• MR85: G. Miller a.i~d J. Reif. Parallel tree contractio~ts and its applications. In Froceedings of the 17t.h Annual A CA'i Symposium, on Theory of Conl, pu~ing, pages 478--489, 1985.
• PR87: V. Pan a.nd .l.t{. R.eif. Fast and efficient, solution of path algebra problems. Technical Report 3, Computer Science Depart, mellt, S'ca~;e University of New York at Albany, 1987.
• SV82: Yossi Shiloach , Uzi Vishkin, An O(n2 log n) parallel max-flow algorithm, Journal of Algorithms, v.3 n.2, p.128-146, Feb. 1982 [doi>10.1016/0196-6774(82)90013-X]
• TV85: R. Tarjan and U. Vishkin. An efficient parallel biconnectivity algorithm. SIAM Journal on Computing, 14(4):862-874, November 1985.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

General Terms:
Algorithms, Theory