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

Fully Dynamic Shortest Paths and Reachability in Sparse Digraphs

Uproszczony widok
cris.lastimport.scopus2024-02-12T20:14:12Z
dc.abstract.enWe study the exact fully dynamic shortest paths problem. For real-weighted directed graphs, we show a deterministic fully dynamic data structure with Õ(mn^{4/5}) worst-case update time processing arbitrary s,t-distance queries in Õ(n^{4/5}) time. This constitutes the first non-trivial update/query tradeoff for this problem in the regime of sparse weighted directed graphs. Moreover, we give a Monte Carlo randomized fully dynamic reachability data structure processing single-edge updates in Õ(n√m) worst-case time and queries in O(√m) time. For sparse digraphs, such a tradeoff has only been previously described with amortized update time [Roditty and Zwick, SIAM J. Comp. 2008].
dc.affiliationUniwersytet Warszawski
dc.conference.countryNiemcy
dc.conference.datefinish2023-07-14
dc.conference.datestart2023-07-10
dc.conference.placePadeborn
dc.conference.seriesInternational Colloquium on Automata Languages and Programming
dc.conference.seriesInternational Colloquium on Automata Languages and Programming
dc.conference.seriesshortcutICALP
dc.conference.shortcutICALP 2023
dc.conference.weblinkhttps://icalp2023.cs.upb.de/
dc.contributor.authorSankowski, Piotr
dc.contributor.authorKarczmarz, Adam
dc.date.accessioned2024-01-25T01:37:52Z
dc.date.available2024-01-25T01:37:52Z
dc.date.copyright2023-07-05
dc.date.issued2023
dc.description.accesstimeAT_PUBLICATION
dc.description.financePublikacja bezkosztowa
dc.description.versionFINAL_PUBLISHED
dc.identifier.doi10.4230/LIPICS.ICALP.2023.84
dc.identifier.urihttps://repozytorium.uw.edu.pl//handle/item/107602
dc.identifier.weblinkhttps://drops.dagstuhl.de/opus/volltexte/2023/18136/
dc.languageeng
dc.pbn.affiliationcomputer and information sciences
dc.relation.pages1-20
dc.rightsCC-BY
dc.sciencecloudnosend
dc.titleFully Dynamic Shortest Paths and Reachability in Sparse Digraphs
dc.typeJournalArticle
dspace.entity.typePublication