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

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

Technical Report, ALCOMFT-TR-01-38, ALCOM-FT, 14 pages, May 2001.


Recently external memory graph algorithms 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. In this paper we develop an improved algorithm for the problem of computing a minimum spanning tree of a general graph, as well as new algorithms for the single source shortest paths and the multi-way graph separation problems on planar graphs.

Online version

alcomft-tr-01-38.pdf (234 Kb)

BIBTEX entry

  author = "Lars Arge and Gerth St{\o}lting Brodal and Laura Toma",
  institution = "ALCOM-FT",
  month = "May",
  number = "ALCOMFT-TR-01-38",
  pages = "14",
  title = "On External Memory {MST}, {SSSP} and Multi-way Planar Graph Separation",
  year = "2001"