Aarhus University Seal / Aarhus Universitets segl

Lars Arge

Multiway simple cycle separators and I/O-efficient algorithms for planar graphs

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

  • L. Arge
  • Freek van Walderveen, Denmark
  • Norbert Zeh
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.
Original languageEnglish
Title of host publicationProceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms
Number of pages18
PublisherSociety for Industrial and Applied Mathematics
Publication year1 Jan 2013
ISBN (Electronic)9781611972511
Publication statusPublished - 1 Jan 2013
EventACM-SIAM Symposium on Discrete Algorithms - New Orleans, United States
Duration: 6 Jan 20138 Jan 2013
Conference number: 24


ConferenceACM-SIAM Symposium on Discrete Algorithms
LandUnited States
ByNew Orleans
SeriesThe Annual A C M - S I A M Symposium on Discrete Algorithms. Proceedings

See relations at Aarhus University Citationformats

ID: 56165864