On External-Memory MST, SSSP and Multi-way Planar Graph Separation

Lars Arge, Gerth Stølting Brodal, and Laura Toma

In Journal of Algorithms, volume 53(2), pages 186-206, 2004.


Recently external memory graph problems have received considerable attention because massive graphs arise naturally in many applications involving massive data sets. Even though a large number of I/O-efficient graph algorithms have been developed, a number of fundamental problems still remain open.

The results in this paper fall in two main classes: First we develop an improved algorithm for the problem of computing a minimum spanning tree (MST) of a general undirected graph. Second we show that on planar undirected graphs the problems of computing a multi-way graph separation and single source shortest paths (SSSP) can be reduced I/O-efficiently to planar breadth-first search (BFS). Since BFS can be trivially reduced to SSSP by assigning all edges weight one, it follows that in external memory planar BFS, SSSP, and multi-way separation are equivalent. That is, if any of these problems can be solved I/O-efficiently, then all of them can be solved I/O-efficiently in the same bound. Our planar graph results have subsequently been used to obtain I/O-efficient algorithms for all fundamental problems on planar undirected graphs.

Copyright notice

Copyright © 2004 by Elsevier Inc.. All rights reserved.

Online version

jalg04.pdf (313 Kb)



BIBTEX entry

  author = "Lars Arge and Gerth St{\o}lting Brodal and Laura Toma",
  doi = "10.1016/j.jalgor.2004.04.001",
  issn = "0196-6774",
  journal = "Journal of Algorithms",
  number = "2",
  pages = "186-206",
  title = "On External-Memory MST, SSSP and Multi-way Planar Graph Separation",
  volume = "53",
  year = "2004"

Other versions