A new deterministic algorithm for fully dynamic all-pairs shortest paths

DOI10.1145/3564246.3585196MaRDI QIDQ6499294zbMATH OpenWikidataFDO

Authors Julia Chuzhoy, Ruimin Zhang

Publication date 8 May 2024

Full work available at URL https://doi.org/10.1145/3564246.3585196

zbMATH Keywords

all-pairs shortest pathfully dynamic algorithm

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems
• A new approach to dynamic all pairs shortest paths
• Algorithm Theory - SWAT 2004
• All-Pairs Almost Shortest Paths
• An On-Line Edge-Deletion Problem
• Approximate distance oracles
• Decremental all-pairs shortest paths in deterministic near-linear time
• Decremental Single-Source Shortest Paths on Undirected Graphs in Near-Linear Total Update Time
• Deterministic Algorithms for Decremental Approximate Shortest Paths: Faster and Simpler
• Deterministic decremental single source shortest paths: beyond the \(O(mn)\) bound
• Dynamic approximate all-pairs shortest paths in undirected graphs
• Dynamic approximate all-pairs shortest paths: breaking the \(O(mn)\) barrier and derandomization
• Dynamic Low-Stretch Spanning Trees in Subpolynomial Time
• Dynamic low-stretch trees via dynamic low-diameter decompositions
• Fully dynamic all-pairs shortest paths: breaking the O(n) barrier
• Fully dynamic randomized algorithms for graph spanners
• Graph partitioning using single commodity flows
• scientific article; zbMATH DE number 1306899 (Why is no real title available?)
• scientific article; zbMATH DE number 7204496 (Why is no real title available?)
• Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
• Improved dynamic algorithms for maintaining approximate shortest paths under deletions
• Maintaining minimum spanning forests in dynamic graphs
• Maintaining shortest paths under deletions in weighted directed graphs
• Near-Linear Time Construction of Sparse Neighborhood Covers
• On dynamic shortest paths problems
• Reliable Hubs for Partially-Dynamic All-Pairs Shortest Paths in Directed Graphs
• Subcubic equivalences between path, matrix, and triangle problems
• Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture

Cited in

(2)

• Are there graphs whose shortest path structure requires large edge weights?
• Bootstrapping dynamic apsp via sparsification

This page was built for publication: A new deterministic algorithm for fully dynamic all-pairs shortest paths

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