Fetching the paper…
Reading the bibliography…
Spanning trees of low average stretch on the non-tree edges, as introduced by Alon et al.
“A Deamortization Approach for Dynamic Spanner and Dynamic Maximal Matching”
Aaron Bernstein, Sebastian Forster and Monika Henzinger · 1918
Earlier work this paper cites.
“Optimum Communication Spanning Trees”
T.. Hu · 1974
Earlier work this paper cites.
“A Reverse Card Shuffle”
David Berman and M.. Klamkin · 1976
Earlier work this paper cites.
“An On-Line Edge-Deletion Problem”
Shimon Even and Yossi Shiloach · 1981
Earlier work this paper cites.
“Complexity of Network Synchronization”
Baruch Awerbuch · 1985
Earlier work this paper cites.
“Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications” Announced at STOC’83
Greg. Frederickson · 1985
Earlier work this paper cites.
“A Graph-Theoretic Game and Its Application to the k k -Server Problem”
Noga Alon, Richard. Karp, David Peleg and Douglas. West · 1995
Earlier work this paper cites.
“Fully Dynamic Biconnectivity and Transitive Closure”
Monika Henzinger and Valerie King · 1995
Earlier work this paper cites.
“Sparsification - a technique for speeding up dynamic graph algorithms” Announced at FOCS’92
David Eppstein, Zvi Galil, Giuseppe. Italiano and Amnon Nissenzweig · 1997
Earlier work this paper cites.
“Deterministic Polylog Approximation for Minimum Communication Spanning Trees”
David Peleg and Eilon Reshef · 1998
Earlier work this paper cites.
“Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs”
Valerie King · 1999
Earlier work this paper cites.
“Maintaining Minimum Spanning Forests in Dynamic Graphs” Announced at ICALP’97
Monika Henzinger and Valerie King · 2001
Earlier work this paper cites.
“Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity” Announced at STOC’98
Jacob Holm, Kristian de Lichtenberg and Mikkel Thorup · 2001
Earlier work this paper cites.
“Support Theory for Preconditioning”
Erik. Boman and Bruce Hendrickson · 2003
Earlier work this paper cites.
“Small Stretch Spanners on Dynamic Graphs” Announced at ESA’05
Giorgio Ausiello, Paolo Franciosa and Giuseppe. Italiano · 2006
Earlier work this paper cites.
“Nearly Tight Low Stretch Spanning Trees”
Ittai Abraham, Yair Bartal and Ofer Neiman · 2008
Earlier work this paper cites.
“Lower-Stretch Spanning Trees” Announced at STOC’05
Michael Elkin, Yuval Emek, Daniel. Spielman and Shang-Hua Teng · 2008
Cited alongside, same era.
“Optimal hierarchical decompositions for congestion minimization in networks”
Harald Räcke · 2008
Cited alongside, same era.
“Interchanging distance and capacity in probabilistic mappings”
Reid Andersen and Uriel Feige · 2009
Cited alongside, same era.
“Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size”
Ankur Moitra · 2009
Cited alongside, same era.
“A Note on Preconditioning by Low-Stretch Spanning Trees”
Daniel. Spielman and Jaeoh Woo · 2009
Cited alongside, same era.
“Approaching Optimality for Solving SDD Linear Systems” Announced at FOCS’10
Ioannis Koutis, Gary. Miller and Richard Peng · 2014
Later among the works it cites.
“Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems” Announced at STOC’04
Daniel. Spielman and Shang-Hua Teng · 2014
Later among the works it cites.
“Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs”
András. Benczúr and David. Karger · 2015
Later among the works it cites.
“Near-Optimal Distributed Maximum Flow”
Mohsen Ghaffari, Andreas Karrenbauer, Fabian Kuhn, Christoph Lenzen and Boaz Patt-Shamir · 2015
Later among the works it cites.
“On Fully Dynamic Graph Sparsifiers”
Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger and Richard Peng · 2016
Later among the works it cites.
“Fully Dynamic Spanners with Worst-Case Update Time”
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
“Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners” Announced at ICALP’07
Michael Elkin · 2011
Cited alongside, same era.
“ k -Outerplanar Graphs, Planar Duality, and Low Stretch Spanning Trees”
Yuval Emek · 2011
Cited alongside, same era.
“A Nearly- m log n m\log n Time Solver for SDD Linear Systems”
Ioannis Koutis, Gary. Miller and Richard Peng · 2011
Cited alongside, same era.
“Using Petal-Decompositions to Build a Low Stretch Spanning Tree”
Ittai Abraham and Ofer Neiman · 2012
Cited alongside, same era.
“Fully dynamic randomized algorithms for graph spanners”
Surender Baswana, Sumeet Khurana and Soumojit Sarkar · 2012
Cited alongside, same era.
“A simple, combinatorial algorithm for solving SDD systems in nearly-linear time”
Jonathan. Kelner, Lorenzo Orecchia, Aaron Sidford and Zeyuan Allen Zhu · 2013
Cited alongside, same era.
“Parallel Graph Decompositions Using Random Shifts”
Gary. Miller, Richard Peng and Shen Xu · 2013
Cited alongside, same era.
Greg Bodwin and Sebastian Krinninger · 2016
Later among the works it cites.
“Dynamic Approximate All-Pairs Shortest Paths: Breaking the O(mn) Barrier and Derandomization” Announced at FOCS’13
Monika Henzinger, Sebastian Krinninger and Danupon Nanongkai · 2016
Later among the works it cites.
“Faster Spectral Sparsification and Numerical Algorithms for SDD Matrices” Announced at STACS’12
Ioannis Koutis, Alex Levin and Richard Peng · 2016
Later among the works it cites.
“Efficient Algorithms for Constructing Very Sparse Spanners and Emulators”
Michael Elkin and Ofer Neiman · 2017
Later among the works it cites.
“Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O ( n 1 / 2 − ϵ ) O(n^{1/2-\epsilon}) time”
Danupon Nanongkai and Thatchaphol Saranurak · 2017
Later among the works it cites.
“Dynamic Minimum Spanning Forest with Subpolynomial Worst-Case Update Time”
Danupon Nanongkai, Thatchaphol Saranurak and Christian Wulff-Nilsen · 2017
Later among the works it cites.
“Fully-dynamic minimum spanning forest with improved worst-case update time”
Christian Wulff-Nilsen · 2017
Later among the works it cites.
“Near-Optimal Approximate Decremental All Pairs Shortest Paths”
Shiri Chechik · 2018
Closest in time.
“Faster Distributed Shortest Path Approximations via Shortcuts”
Bernhard Haeupler and Jason Li · 2018
Closest in time.
“Expander Decomposition and Pruning: Faster, Stronger, and Simpler”
Thatchaphol Saranurak and Di Wang · 2019
Closest in time.