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

DOI10.4230/LIPICS.ESA.2019.65MaRDI QIDQ5075810zbMATH OpenOpenAlexFDO

Authors Adam Karczmarz, Jakub Łącki

Publication date 11 May 2022

Full work available at URL https://arxiv.org/abs/1907.02266

zbMATH Keywords

decrementaldirected graphsdynamichubsincrementalshortest paths

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Recommendations

• Fully dynamic all pairs shortest paths with real edge weights
• Maintaining shortest paths under deletions in weighted directed graphs
• A new approach to dynamic all pairs shortest paths
• Maintaining shortest paths under deletions in weighted directed graphs
• A new approach to dynamic all pairs shortest paths

Cites work

• A data structure for dynamic trees
• A new approach to dynamic all pairs shortest paths
• A subquadratic-time algorithm for decremental single-source shortest paths
• All pairs shortest paths using bridging sets and rectangular matrix multiplication
• An On-Line Edge-Deletion Problem
• Dynamic approximate all-pairs shortest paths in undirected graphs
• Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
• Dynamic graph connectivity in polylogarithmic worst case time
• Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm
• Faster deterministic fully-dynamic graph connectivity
• Fully dynamic all pairs shortest paths with real edge weights
• Fully dynamic all-pairs shortest paths with worst-case update-time revisited
• High-Probability Parallel Transitive-Closure Algorithms
• scientific article; zbMATH DE number 432746 (Why is no real title available?)
• scientific article; zbMATH DE number 1263228 (Why is no real title available?)
• scientific article; zbMATH DE number 1306899 (Why is no real title available?)
• Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs
• Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
• Improved dynamic algorithms for maintaining approximate shortest paths under deletions
• Improved Dynamic Reachability Algorithms for Directed Graphs
• Maintaining shortest paths under deletions in weighted directed graphs
• Near-optimal fully-dynamic graph connectivity
• On dynamic shortest paths problems
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs

Cited in

(8)

• Single-source shortest paths and strong connectivity in dynamic planar graphs
• Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs.
• A new deterministic algorithm for fully dynamic all-pairs shortest paths
• Deterministic incremental APSP with polylogarithmic update time and stretch
• New tradeoffs for decremental approximate all-pairs shortest paths
• Decremental APSP in unweighted digraphs versus an adaptive adversary
• Fully dynamic algorithms for minimum weight cycle and related problems
• On incremental approximate shortest paths in directed graphs

This page was built for publication: Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5075810)