Fetching the paper…
Reading the bibliography…
We study the decremental All-Pairs Shortest Paths (APSP) problem in undirected edge-weighted graphs.
An on-line edge-deletion problem
Shimon Even and Yossi Shiloach · 1981
Earlier work this paper cites.
Sparse partitions
Baruch Awerbuch and David Peleg · 1990
Earlier work this paper cites.
Approximate max-flow min-(multi)-cut theorems and their applications
N. Garg, V.V. Vazirani, and M. Yannakakis · 1995
Earlier work this paper cites.
Fully dynamic biconnectivity and transitive closure
Monika Rauch Henzinger and Valerie King · 1995
Earlier work this paper cites.
Near-linear time construction of sparse neighborhood covers
Baruch Awerbuch, Bonnie Berger, Lenore Cowen, and David Peleg · 1998
Earlier work this paper cites.
Faster and simpler algorithms for multicommodity flow and other fractional packing problems
Naveen Garg and Jochen Könemann · 1998
Earlier work this paper cites.
All pairs shortest paths in weighted directed graphs-exact and almost exact algorithms
Uri Zwick · 1998
Earlier work this paper cites.
Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
F. T. Leighton and S. Rao · 1999
Earlier work this paper cites.
All-pairs almost shortest paths
Dorit Dor, Shay Halperin, and Uri Zwick · 2000
Earlier work this paper cites.
Approximating fractional multicommodity flow independent of the number of commodities
Lisa Fleischer · 2000
Earlier work this paper cites.
Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup · 2001
Earlier work this paper cites.
Approximate distance oracles
M. Thorup and U. Zwick · 2001
Earlier work this paper cites.
Dinitz’ algorithm: The original version and Even’s version
Yefim Dinitz · 2006
Earlier work this paper cites.
Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
Surender Baswana, Ramesh Hariharan, and Sandeep Sen · 2007
Earlier work this paper cites.
On a cut-matching game for the sparsest cut problem
Rohit Khandekar, Subhash Khot, Lorenzo Orecchia, and Nisheeth K Vishnoi · 2007
Earlier work this paper cites.
Graph partitioning using single commodity flows
Rohit Khandekar, Satish Rao, and Umesh Vazirani · 2009
Earlier work this paper cites.
Faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms
Aleksander Madry · 2010
Cited alongside, same era.
Improved dynamic algorithms for maintaining approximate shortest paths under deletions
Aaron Bernstein and Liam Roditty · 2011
Cited alongside, same era.
On dynamic shortest paths problems
Liam Roditty and Uri Zwick · 2011
Cited alongside, same era.
The multiplicative weights update method: a meta-algorithm and applications
Sanjeev Arora, Elad Hazan, and Satyen Kale · 2012
Cited alongside, same era.
Fully dynamic randomized algorithms for graph spanners
Surender Baswana, Sumeet Khurana, and Soumojit Sarkar · 2012
Cited alongside, same era.
Faster approximate multicommodity flow using quadratically coupled flows
Jonathan A. Kelner, Gary L. Miller, and Richard Peng · 2012
Deterministic partially dynamic single source shortest paths in weighted graphs
Aaron Bernstein · 2017
Later among the works it cites.
Near-optimal approximate decremental all pairs shortest paths
Shiri Chechik · 2018
Later among the works it cites.
Subcubic equivalences between path, matrix, and triangle problems
Virginia Vassilevska Williams and R Ryan Williams · 2018
Later among the works it cites.
Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Saranurak · 2019
Later among the works it cites.
A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems
Julia Chuzhoy and Sanjeev Khanna · 2019
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
Dynamic approximate all-pairs shortest paths in undirected graphs
Liam Roditty and Uri Zwick · 2012
Cited alongside, same era.
Fully dynamic all-pairs shortest paths: Breaking the O (n) barrier
Ittai Abraham, Shiri Chechik, and Kunal Talwar · 2014
Cited alongside, same era.
Decremental single-source shortest paths on undirected graphs in near-linear total update time
Sebastian Forster, Monika Henzinger, and Danupon Nanongkai · 2014
Cited alongside, same era.
A subquadratic-time algorithm for decremental single-source shortest paths
Sebastian Forster, Monika Henzinger, and Danupon Nanongkai · 2014
Cited alongside, same era.
Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak · 2015
Cited alongside, same era.
Deterministic decremental single source shortest paths: beyond the O(mn) bound
Aaron Bernstein and Shiri Chechik · 2016
Cited alongside, same era.
Dynamic low-stretch trees via dynamic low-diameter decompositions
Sebastian Forster and Gramoz Goranci · 2019
Later among the works it cites.
Reliable hubs for partially-dynamic all-pairs shortest paths in directed graphs
Adam Karczmarz and Jakub Łacki · 2019
Later among the works it cites.
Expander decomposition and pruning: Faster, stronger, and simpler
Thatchaphol Saranurak and Di Wang · 2019
Later among the works it cites.
Fully-dynamic graph sparsifiers against an adaptive adversary
Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun · 2020
Later among the works it cites.
New techniques and fine-grained hardness for dynamic near-additive spanners
Thiago Bergamaschi, Monika Henzinger, Maximilian Probst Gutenberg, Virginia Vassilevska Williams, and Nicole Wein · 2020
Later among the works it cites.
Dynamic low-stretch spanning trees in subpolynomial time
Shiri Chechik and Tianyi Zhang · 2020
Later among the works it cites.
Dynamic maintenance of low-stretch probabilistic tree embeddings with applications
Sebastian Forster, Gramoz Goranci, and Monika Henzinger · 2020
Later among the works it cites.
Deterministic algorithms for decremental approximate shortest paths: Faster and simpler
Maximilian Probst Gutenberg and Christian Wulff-Nilsen · 2020
Later among the works it cites.
Near-optimal decremental approximate multi-source shortest paths
Jakub Łacki and Yasamin Nazari · 2020
Later among the works it cites.
Deterministic algorithms for decremental shortest paths via layered core decomposition
Julia Chuzhoy and Thatchaphol Saranurak · 2021
Closest in time.