License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.61
URN: urn:nbn:de:0030-drops-90654
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9065/
Gawrychowski, Pawel ;
Karczmarz, Adam
Improved Bounds for Shortest Paths in Dense Distance Graphs
Abstract
We study the problem of computing shortest paths in so-called dense distance graphs, a basic building block for designing efficient planar graph algorithms. Let G be a plane graph with a distinguished set partial{G} of boundary vertices lying on a constant number of faces of G. A distance clique of G is a complete graph on partial{G} encoding all-pairs distances between these vertices. A dense distance graph is a union of possibly many unrelated distance cliques.
Fakcharoenphol and Rao [Fakcharoenphol and Rao, 2006] proposed an efficient implementation of Dijkstra's algorithm (later called FR-Dijkstra) computing single-source shortest paths in a dense distance graph. Their algorithm spends O(b log^2{n}) time per distance clique with b vertices, even though a clique has b^2 edges. Here, n is the total number of vertices of the dense distance graph. The invention of FR-Dijkstra was instrumental in obtaining such results for planar graphs as nearly-linear time algorithms for multiple-source-multiple-sink maximum flow and dynamic distance oracles with sublinear update and query bounds.
At the heart of FR-Dijkstra lies a data structure updating distance labels and extracting minimum labeled vertices in O(log^2{n}) amortized time per vertex. We show an improved data structure with O((log^2{n})/(log^2 log n)) amortized bounds. This is the first improvement over the data structure of Fakcharoenphol and Rao in more than 15 years. It yields improved bounds for all problems on planar graphs, for which computing shortest paths in dense distance graphs is currently a bottleneck.
BibTeX - Entry
@InProceedings{gawrychowski_et_al:LIPIcs:2018:9065,
author = {Pawel Gawrychowski and Adam Karczmarz},
title = {{Improved Bounds for Shortest Paths in Dense Distance Graphs}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {61:1--61:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-076-7},
ISSN = {1868-8969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9065},
URN = {urn:nbn:de:0030-drops-90654},
doi = {10.4230/LIPIcs.ICALP.2018.61},
annote = {Keywords: shortest paths, dense distance graph, planar graph, Monge matrix}
}
|
Keywords: |
|
shortest paths, dense distance graph, planar graph, Monge matrix |
|
Collection: |
|
45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
04.07.2018 |
