Fetching the paper…
Reading the bibliography…
We study \emph{dynamic} algorithms for maintaining spectral vertex sparsifiers of graphs with respect to a set of terminals $T$ of our choice.
Random walks, universal traversal sequences, and the complexity of maze problems
R. Aleliunas, R. J. Lipton, L. Lovasz, C. Rackoff, and R. M. Karp · 1979
Earlier work this paper cites.
Random Walks and Electric Networks
Peter G. Doyle and J. Laurie Snell · 1984
Earlier work this paper cites.
Data structures for on-line updating of minimum spanning trees, with applications
Greg N Frederickson · 1985
Earlier work this paper cites.
Graph spanners
David Peleg and Alejandro A Schäffer · 1989
Earlier work this paper cites.
Offline algorithms for dynamic minimum spanning tree problems
David Eppstein · 1991
Earlier work this paper cites.
Short random walks on graphs
Greg Barnes and Uriel Feige · 1996
Earlier work this paper cites.
Approximating s-t minimum cuts in O ~ ( n 2 ) \tilde{O}(n^{2}) time
Andras A. Benczur and David R. Karger · 1996
Earlier work this paper cites.
Sparsification: a technique for speeding up dynamic graph algorithms
David Eppstein, Zvi Galil, Giuseppe F Italiano, and Amnon Nissenzweig · 1997
Earlier work this paper cites.
A static 2 2 -approximation algorithm for vertex connectivity and incremental approximation algorithms for edge and vertex connectivity
Monika Rauch Henzinger · 1997
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.
The link prediction problem for social networks
David Liben-Nowell and Jon M. Kleinberg · 2003
Earlier work this paper cites.
A new approach to dynamic all pairs shortest paths
Camil Demetrescu and Giuseppe F. Italiano · 2004
Earlier work this paper cites.
A tight bound on approximating arbitrary metrics by tree metrics
Jittat Fakcharoenphol, Satish Rao, and Kunal Talwar · 2004
Earlier work this paper cites.
Dynamic transitive closure via dynamic matrix inverse (extended abstract)
Piotr Sankowski · 2004
Earlier work this paper cites.
Fully-dynamic min-cut
Mikkel Thorup · 2007
Earlier work this paper cites.
Optimal hierarchical decompositions for congestion minimization in networks
Harald Räcke · 2008
Earlier work this paper cites.
Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size
Ankur Moitra · 2009
Earlier work this paper cites.
Vertex sparsifiers and abstract rounding algorithms
Moses Charikar, Tom Leighton, Shi Li, and Ankur Moitra · 2010
Earlier work this paper cites.
Fast approximation algorithms for cut-based problems in undirected graphs
Aleksander Madry · 2010
Earlier work this paper cites.
Metric extension operators, vertex sparsifiers and lipschitz extendability
Konstantin Makarychev and Yury Makarychev · 2010
Earlier work this paper cites.
Maintaining a large matching and a small vertex cover
Krzysztof Onak and Ronitt Rubinfeld · 2010
Earlier work this paper cites.
Algorithms, Graph Theory, and Linear Equations in Laplacian Matrices
Daniel A. Spielman · 2010
Earlier work this paper cites.
The Laplacian Paradigm: Emerging Algorithms for Massive Graphs
Shang-Hua Teng · 2010
Earlier work this paper cites.
A nearly-m log n time solver for SDD linear systems
Ioannis Koutis, Gary L. Miller, and Richard Peng · 2011
Earlier work this paper cites.
Min-cuts and shortest cycles in planar graphs in o (n loglogn) time
Jakub Lacki and Piotr Sankowski · 2011
Earlier work this paper cites.
Spectral sparsification of graphs
D. Spielman and S. Teng · 2011
Cited alongside, same era.
Graph sparsification by effective resistances
Daniel Spielman and Nikhil Srivastava · 2011
Cited alongside, same era.
Fully dynamic randomized algorithms for graph spanners
Surender Baswana, Sumeet Khurana, and Soumojit Sarkar · 2012
Cited alongside, same era.
User-friendly tail bounds for sums of random matrices
Joel A. Tropp · 2012
Cited alongside, same era.
Spectral sparsification of graphs: theory and algorithms
Joshua Batson, Daniel A. Spielman, Nikhil Srivastava, and Shang-Hua Teng · 2013
Cited alongside, same era.
Kron reduction of graphs with applications to electrical networks
Florian Dörfler and Francesco Bullo · 2013
Cited alongside, same era.
Dynamic approximate all-pairs shortest paths: Breaking the O(mn) barrier and derandomization
Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai · 2016
Later among the works it cites.
Faster spectral sparsification and numerical algorithms for SDD matrices
Ioannis Koutis, Alex Levin, and Richard Peng · 2016
Later among the works it cites.
Sparsified cholesky and multigrid solvers for connection laplacians
Rasmus Kyng, Yin Tat Lee, Richard Peng, Sushant Sachdeva, and Daniel A Spielman · 2016
Later among the works it cites.
Approximate gaussian elimination for laplacians-fast, sparse, and simple
Rasmus Kyng and Sushant Sachdeva · 2016
Later among the works it cites.
Simple deterministic algorithms for fully dynamic maximal matching
Ofer Neiman and Shay Solomon · 2016
Later among the works it cites.
Fully dynamic maximal matching in constant update time
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Fully dynamic ( 1 + ϵ ) (1+\epsilon) -approximate matchings
Manoj Gupta and Richard Peng · 2013
Cited alongside, same era.
Dynamic graph connectivity in polylogarithmic worst case time
Bruce M Kapron, Valerie King, and Ben Mountjoy · 2013
Cited alongside, same era.
Mimicking networks and succinct representations of terminal cuts
Robert Krauthgamer and Inbal Rika · 2013
Cited alongside, same era.
Approximate maximum flow on separable undirected graphs
Gary L. Miller and Richard Peng · 2013
Cited alongside, same era.
Nearly maximum flows in nearly linear time
Jonah Sherman · 2013
Cited alongside, same era.
Towards ( 1 + ϵ ) (1+\epsilon) -approximate flow sparsifiers
Alexandr Andoni, Anupam Gupta, and Robert Krauthgamer · 2014
Cited alongside, same era.
Shay Solomon · 2016
Later among the works it cites.
Fully dynamic all-pairs shortest paths with worst-case update-time revisited
Ittai Abraham, Shiri Chechik, and Sebastian Krinninger · 2017
Later among the works it cites.
Sampling random spanning trees faster than matrix multiplication
David Durfee, Rasmus Kyng, John Peebles, Anup B Rao, and Sushant Sachdeva · 2017
Later among the works it cites.
Determinant-preserving sparsification of SDDM matrices with applications to counting and sampling spanning trees
David Durfee, John Peebles, Richard Peng, and Anup B. Rao · 2017
Later among the works it cites.
The power of vertex sparsifiers in dynamic graph algorithms
Gramoz Goranci, Monika Henzinger, and Pan Peng · 2017
Later among the works it cites.
Density independent algorithms for sparsifying k-step random walks
Gorav Jindal, Pavel Kolev, Richard Peng, and Saurabh Sawlani · 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.
Offline dynamic higher connectivity
Richard Peng, Bryce Sandlund, and Daniel Dominic Sleator · 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.
Dynamic effective resistances and approximate schur complement on separable graphs
Gramoz Goranci, Monika Henzinger, and Pan Peng · 2018
Later among the works it cites.
Dynamic low-stretch trees via dynamic low-diameter decompositions
Gramoz Goranci and Sebastian Krinninger · 2018
Later among the works it cites.
Kirchhoff index as a measure of edge centrality in weighted networks: Nearly linear time algorithms
Huan Li and Zhongzhi Zhang · 2018
Later among the works it cites.
Graph reduction by local variation
Andreas Loukas · 2018
Later among the works it cites.
Spectrally approximating large graphs with smaller graphs
Andreas Loukas and Pierre Vandergheynst · 2018
Later among the works it cites.
An almost-linear time algorithm for uniform random spanning tree generation
Aaron Schild · 2018
Later among the works it cites.
Localization of electrical flows
Aaron Schild, Satish Rao, and Nikhil Srivastava · 2018
Later among the works it cites.
Semi-supervised learning on data streams via temporal label propagation
Tal Wagner, Sudipto Guha, Shiva Prasad Kasiviswanathan, and Nina Mishra · 2018
Later among the works it cites.
On solving linear systems in sublinear time
Alexandr Andoni, Robert Krauthgamer, and Yosef Pogrow · 2019
Closest in time.