Gawrychowski, Pawel ;
Karczmarz, Adam
Improved Bounds for Shortest Paths in Dense Distance Graphs
Abstract
We study the problem of computing shortest paths in socalled 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 allpairs 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 FRDijkstra) computing singlesource 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 FRDijkstra was instrumental in obtaining such results for planar graphs as nearlylinear time algorithms for multiplesourcemultiplesink maximum flow and dynamic distance oracles with sublinear update and query bounds.
At the heart of FRDijkstra 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:161:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770767},
ISSN = {18688969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9065},
URN = {urn:nbn:de:0030drops90654},
doi = {10.4230/LIPIcs.ICALP.2018.61},
annote = {Keywords: shortest paths, dense distance graph, planar graph, Monge matrix}
}
2018
Keywords: 

shortest paths, dense distance graph, planar graph, Monge matrix 
Seminar: 

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Issue date: 

2018 
Date of publication: 

2018 