^{1} Aarhus University^{2} Department of Computer Science, Science and Technology, Aarhus University^{3} Department of Computer Science - Center for Massive Data Algoritmics, Department of Computer Science, Science and Technology, Aarhus University^{4} Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University^{5} Department of Computer Science, Science and Technology, Aarhus University

Abstract:

We revisit I/O-efficient solutions to a number of fundamental problems on planar graphs: single-source shortest paths, topological sorting, and computing strongly connected components. Existing I/O-efficient solutions to these problems pay for I/O efficiency using excessive computation time in internal memory, thereby completely negating the performance gain achieved by minimizing the number of disk accesses. In this paper, we show how to make these algorithms simultaneously efficient in internal and external memory so they achieve I/O complexity O(sort(N)) and take O(N log N) time in internal memory, where sort(N) is the number of I/Os needed to sort N items in external memory. The key, and the main technical contribution of this paper, is a multiway version of Miller's simple cycle separator theorem. We show how to compute these separators in linear time in internal memory, and using O(sort(N)) I/Os and O(N log N) (internal-memory computation) time in external memory.

ISBN:

9781611972511

Type:

Conference paper

Language:

English

Published in:

Proceedings of the Annual Acm-siam Symposium on Discrete Algorithms, 2013, p. 901-918

Main Research Area:

Science/technology

Publication Status:

Published

Series:

Annual a C M - S I a M Symposium on Discrete Algorithms. Proceedings

Review type:

Peer Review

Conference:

ACM-SIAM Symposium on Discrete AlgorithmsSymposium on Discrete Algorithms, 2013