ALCOMFT-TR-01-38

Lars Arge, Gerth Stølting Brodal and Laura Toma
On External-Memory MST, SSSP and Multi-way Planar Graph Separation
Århus. Work packages 1 and 4. April 2001.

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.

Postscript file: ALCOMFT-TR-01-38.ps.gz (194 kb).