I/O-efficient topological sorting of planar DAGs

ABSTRACT

We present algorithms that solve a number of fundamental problems on planar directed graphs (planar digraphs) in O((N)) I/Os, where (N) is the number of I/Os needed to sort N elements. The problems we consider are breadth-first search, the single-source shortest path problem, computing a directed ear decomposition of a strongly connected planar digraph, computing an open directed ear decomposition of a strongly connected biconnected planar digraph, and topologically sorting a planar directed acyclic graph.

REFERENCES

• 1: Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
• 2: Lars Arge, The Buffer Tree: A New Technique for Optimal I/O-Algorithms (Extended Abstract), Proceedings of the 4th International Workshop on Algorithms and Data Structures, p.334-345, August 16-18, 1995
• 3: Lars Arge , Gerth Stølting Brodal , Laura Toma, On External-Memory MST, SSSP, and Multi-way Planar Graph Separation, Proceedings of the 7th Scandinavian Workshop on Algorithm Theory, p.433-447, July 05-07, 2000
• 4: Lars Arge , Ulrich Meyer , Laura Toma , Norbert Zeh, On External-Memory Planar Depth First Search, Proceedings of the 7th International Workshop on Algorithms and Data Structures, p.471-482, August 08-10, 2001
• 5: Adam L. Buchsbaum , Michael Goldwasser , Suresh Venkatasubramanian , Jeffery R. Westbrook, On external memory graph traversal, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.859-860, January 09-11, 2000, San Francisco, California, United States
• 6: Yi-Jen Chiang , Michael T. Goodrich , Edward F. Grove , Roberto Tamassia , Darren Erik Vengroff , Jeffrey Scott Vitter, External-memory graph algorithms, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.139-149, January 22-24, 1995, San Francisco, California, United States
• 7: E. W. Dijkstra. A note on two problems in connection with graphs. Numerical Mathematics, 1:269--271, 1959.
• 8: M. T. Goodrich, J.-J. Tsay, D. E. Vengroff, and J. S. Vitter. External-memory computational geometry. In Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, pages 714--723, November 1993.
• 9: David Hutchinson , Anil Maheshwari , Norbert Zeh, An external memory data structure for shortest path queries, Discrete Applied Mathematics, v.126 n.1, p.55-82, March 2003 [doi>10.1016/S0166-218X(02)00217-2]
• 10: Ming-Yang Kao, Linear-processor NC algorithms for planar directed graphs I: strongly connected components, SIAM Journal on Computing, v.22 n.3, p.431-459, June 1993 [doi>10.1137/0222032]
• 11: Ming-Yang Kao , Philip N. Klein, Towards overcoming the transitive-closure bottleneck: efficient parallel algorithms for planar digraphs, Journal of Computer and System Sciences, v.47 n.3, p.459-500, Dec. 1993 [doi>10.1016/0022-0000(93)90042-U]
• 12: Ming-Yang Kao , Gregory E. Shannon, Linear-processor NC algorithms for planar directed graphs II: directed spanning trees, SIAM Journal on Computing, v.22 n.3, p.460-481, June 1993 [doi>10.1137/0222033]
• 13: Vijay Kumar , Eric J. Schwabe, Improved Algorithms and Data Structures for Solving Graph Problems in External Memory, Proceedings of the 8th IEEE Symposium on Parallel and Distributed Processing (SPDP '96), p.169, October 23-26, 1996
• 14: Anil Maheshwari , Norbert Zeh, I/O-optimal algorithms for planar graphs using separators, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.372-381, January 06-08, 2002, San Francisco, California
• 15: Yael Maon , Baruch Schieber , Uzi Vishkin, Parallel ear decomposition search (EDS) and st-numbering in graphs, Theoretical Computer Science, v.47 n.3, p.277-298, Nov., 1986
• 16: Kurt Mehlhorn , Ulrich Meyer, External-Memory Breadth-First Search with Sublinear I/O, Proceedings of the 10th Annual European Symposium on Algorithms, p.723-735, September 17-21, 2002
• 17: Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001 [doi>10.1145/384192.384193]
• 18: Norbert Ralf Zeh , Anil Maheshwari , Jorg-Rudiger Sack, I/o-efficient algorithms for shortest path related problems, 2002

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
I/O-efficient algorithms, ear decomposition, graph algorithms, planar directed graphs, topological sorting