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

Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs

Uproszczony widok
dc.abstract.enWe give new partially-dynamic algorithms for the all-pairs shortest paths problem in weighted directed graphs. Most importantly, we give a new deterministic incremental algorithm for the problem that handles updates in O~(mn^(4/3) log{W}/epsilon) total time (where the edge weights are from [1,W]) and explicitly maintains a (1+epsilon)-approximate distance matrix. For a fixed epsilon>0, this is the first deterministic partially dynamic algorithm for all-pairs shortest paths in directed graphs, whose update time is o(n^2) regardless of the number of edges. Furthermore, we also show how to improve the state-of-the-art partially dynamic randomized algorithms for all-pairs shortest paths [Baswana et al. STOC'02, Bernstein STOC'13] from Monte Carlo randomized to Las Vegas randomized without increasing the running time bounds (with respect to the O~(*) notation). Our results are obtained by giving new algorithms for the problem of dynamically maintaining hubs, that is a set of O~(n/d) vertices which hit a shortest path between each pair of vertices, provided it has hop-length Omega(d). We give new subquadratic deterministic and Las Vegas algorithms for maintenance of hubs under either edge insertions or deletions.
dc.affiliationUniwersytet Warszawski
dc.conference.countryNiemcy
dc.conference.datefinish2019-09-13
dc.conference.datestart2019-09-09
dc.conference.placeMonachium
dc.conference.seriesEuropean Symposium on Algorithms
dc.conference.seriesEuropean Symposium on Algorithms
dc.conference.seriesshortcutESA
dc.conference.shortcutESA 2019
dc.conference.weblinkhttp://esa-symposium.org/
dc.contributor.authorŁącki, Jakub
dc.contributor.authorKarczmarz, Adam
dc.date.accessioned2024-01-25T19:10:49Z
dc.date.available2024-01-25T19:10:49Z
dc.date.copyright2019-09-06
dc.date.issued2019
dc.description.accesstimeAT_PUBLICATION
dc.description.financeNie dotyczy
dc.description.versionFINAL_PUBLISHED
dc.identifier.doi10.4230/LIPICS.ESA.2019.65
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/118314
dc.identifier.weblinkhttps://drops.dagstuhl.de/opus/volltexte/2019/11186/
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages65:1--65:15
dc.rightsCC-BY
dc.sciencecloudnosend
dc.titleReliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
dc.typeJournalArticle
dspace.entity.typePublication