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
E
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
PublisherSpringer
Publication year2004
Pages146-157
ISBN (print)978-3-540-22849-3
DOIs
Publication statusPublished - 2004
EventInternational Colloquium on Automata, Languages, and Programming. ICALP '04 - Turku, Finland
Duration: 12 Jul 200416 Jul 2004
Conference number: 31

Conference

ConferenceInternational Colloquium on Automata, Languages, and Programming. ICALP '04
Nummer31
LandFinland
ByTurku
Periode12/07/200416/07/2004
SeriesLecture Notes in Computer Science
Volume3142

See relations at Aarhus University Citationformats

ID: 280046