Artykuł w czasopiśmie
Brak miniatury
Licencja
CC-BYCC-BY - Uznanie autorstwa
 

Improved bounds for shortest paths in dense distance graphs

Uproszczony widok
cris.lastimport.scopus2024-02-12T20:50:43Z
dc.abstract.enWe 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.
dc.affiliationUniwersytet Warszawski
dc.conference.countryCzechy
dc.conference.datefinish2018-07-13
dc.conference.datestart2018-07-09
dc.conference.placePraha
dc.conference.seriesInternational Colloquium on Automata Languages and Programming
dc.conference.seriesInternational Colloquium on Automata Languages and Programming
dc.conference.seriesshortcutICALP
dc.conference.shortcutICALP 2018
dc.conference.weblinkhttps://iuuk.mff.cuni.cz/events/icalp2018/
dc.contributor.authorKarczmarz, Adam
dc.contributor.authorGawrychowski, Paweł
dc.date.accessioned2024-01-25T03:57:42Z
dc.date.available2024-01-25T03:57:42Z
dc.date.copyright2018-07-04
dc.date.issued2018
dc.description.accesstimeAT_PUBLICATION
dc.description.financeNie dotyczy
dc.description.versionFINAL_PUBLISHED
dc.identifier.doi10.4230/LIPICS.ICALP.2018.61
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/109094
dc.identifier.weblinkhttps://doi.org/10.4230/LIPIcs.ICALP.2018.61
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages61:1-61:15
dc.rightsCC-BY
dc.sciencecloudnosend
dc.subject.enshortest paths
dc.subject.endense distance graph
dc.subject.enplanar graph
dc.subject.enMonge matrix
dc.titleImproved bounds for shortest paths in dense distance graphs
dc.typeJournalArticle
dspace.entity.typePublication