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

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

In Proc. 7th Scandinavian Workshop on Algorithm Theory, volume 1851 of Lecture Notes in Computer Science, pages 433-447. Springer Verlag, Berlin, 2000.

Abstract

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.

Copyright notice

© Springer-Verlag Berlin Heidelberg 2000. All rights reserved.

Online version

swat00mst.pdf (294 Kb)

DOI

10.1007/3-540-44985-X_37

Links

• Springer Verlag
• Lecture Notes in Computer Science

BIBT_EX entry

@incollection{swat00mst,
  author = "Lars Arge and Gerth Stølting Brodal and Laura Toma",
  booktitle = "Proc. 7th Scandinavian Workshop on Algorithm Theory",
  doi = "10.1007/3-540-44985-X_37",
  isbn = "978-3-540-67690-4",
  pages = "433-447",
  publisher = "Springer {V}erlag, Berlin",
  series = "Lecture Notes in Computer Science",
  title = "On External Memory {MST}, {SSSP} and Multi-way Planar Graph Separation",
  volume = "1851",
  year = "2000"
}