Aarhus University Seal / Aarhus Universitets segl

Lars Arge

External Memory Algorithms for Diameter and All-Pair Shortest-Paths on Sparse Graphs

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

  • Lars Arge
  • Ulrich Meyer, Denmark
  • Laura Toma, Denmark
  • Department of Computer Science
We present several new external-memory algorithms
for finding all-pairs shortest paths in a V -node, Eedge
undirected graph. For all-pairs shortest paths and
diameter in unweighted undirected graphs we present
cache-oblivious algorithms with O(V · E
B logM
B) I/Os,
where B is the block-size and M is the size of internal
memory. For weighted undirected graphs we present
a cache-aware APSP algorithm that performs O(V ·
( V E
B +E
B log E
B )) I/Os. We also present efficient cacheaware
algorithms that find paths between all pairs of
vertices in an unweighted graph with lengths within a
small additive constant of the shortest path length.
All of our results improve earlier results known for
these problems. For approximate APSP we provide
the first nontrivial results. Our diameter result uses
O(V + E) extra space, and all of our other algorithms
use O(V 2) space.
Original languageEnglish
Title of host publicationAutomata, Languages and Programming : 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004. Proceedings
EditorsJosep Diaz, Juhani Karhumäki, Arto Lepistö, Donald Sannella
Number of pages12
Publication year2004
ISBN (print)978-3-540-22849-3
Publication statusPublished - 2004
EventInternational Colloquium on Automata, Languages, and Programming. ICALP '04 - Turku, Finland
Duration: 12 Jul 200416 Jul 2004
Conference number: 31


ConferenceInternational Colloquium on Automata, Languages, and Programming. ICALP '04
SeriesLecture Notes in Computer Science

See relations at Aarhus University Citationformats

ID: 280046