Fetching the paper…
Reading the bibliography…
We initiate the study of dynamic algorithms for graph sparsification problems and obtain fully dynamic algorithms, allowing both edge insertions and edge deletions, that take polylogarithmic time after each update in the graph.
“Graph Sparsification by Effective Resistances” Announced at STOC’08
Daniel˜A. Spielman and Nikhil Srivastava · 1926
Earlier work this paper cites.
“An On-Line Edge-Deletion Problem”
Shimon Even and Yossi Shiloach · 1981
Earlier work this paper cites.
“Randomized Fully Dynamic Graph Algorithms with Polylogarithmic Time per Operation” Announced at STOC’95
Monika˜Rauch Henzinger and Valerie King · 1999
Earlier work this paper cites.
“Minimum Cuts in Near-linear Time” Announced at STOC’96
David˜R. Karger · 2000
Earlier work this paper cites.
“Dynamic Graph Algorithms with Applications”
Mikkel Thorup and David˜R. Karger · 2000
Earlier work this paper cites.
“Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2 2 -Edge, and Biconnectivity” Announced at STOC’98
Jacob Holm, Kristian Lichtenberg and Mikkel Thorup · 2001
Earlier work this paper cites.
“Local Graph Partitioning using PageRank Vectors”
Reid Andersen, Fan Chung and Kevin Lang · 2006
Earlier work this paper cites.
“Fully-Dynamic Min-Cut” Announced at STOC’01
Mikkel Thorup · 2007
Earlier work this paper cites.
“Lower-stretch spanning trees”
Michael Elkin, Yuval Emek, Daniel˜A. Spielman and Shang-Hua Teng · 2008
Earlier work this paper cites.
“Graph Sparsification in the Semi-streaming Model”
Kook˜Jin Ahn and Sudipto Guha · 2009
Earlier work this paper cites.
“Finding Sparse Cuts Locally Using Evolving Sets”
Reid Andersen and Yuval Peres · 2009
Earlier work this paper cites.
“Introduction to Algorithms, Third Edition”
Thomas˜H. Cormen, Charles˜E. Leiserson, Ronald˜L. Rivest and Clifford Stein · 2009
Earlier work this paper cites.
“A Linear-Time Algorithm for Broadcast Domination in a Tree”
John Dabney, Brian˜C. Dean and Stephen˜T. Hedetniemi · 2009
Earlier work this paper cites.
“An O ( l o g ( n ) ) O(log(n)) Fully Dynamic Algorithm for Maximum matching in a tree”
Manoj Gupta and Ankit Sharma · 2009
Earlier work this paper cites.
“Breaking the Multicommodity Flow Barrier for O ( log n ) O(\sqrt{}\log n) -Approximations to Sparsest Cut”
Jonah Sherman · 2009
Earlier work this paper cites.
“Fast Approximation Algorithms for Cut-Based Problems in Undirected Graphs”
Aleksander Madry · 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.
“Towards Polynomial Lower Bounds for Dynamic Problems”
Mihai Patrascu · 2010
Earlier work this paper cites.
“A General Framework for Graph Sparsification”
Wai˜Shing Fung, Ramesh Hariharan, Nicholas J.˜A. Harvey and Debmalya Panigrahi · 2011
Earlier work this paper cites.
“Towards an SDP-based Approach to Spectral Methods: A Nearly-Linear-Time Algorithm for Graph Partitioning and Decomposition”
Lorenzo Orecchia and Nisheeth˜K. Vishnoi · 2011
Earlier work this paper cites.
“Spectral Sparsification of Graphs” Announced at STOC’04
Daniel˜A. Spielman and Shang-Hua Teng · 2011
Earlier work this paper cites.
“Analyzing graph structure via linear measurements”
Kook˜Jin Ahn, Sudipto Guha and Andrew McGregor · 2012
Earlier work this paper cites.
“Graph sketches: sparsification, spanners, and subgraphs”
Kook˜Jin Ahn, Sudipto Guha and Andrew McGregor · 2012
Cited alongside, same era.
“A Sublinear Time Algorithm for PageRank Computations”
Christian Borgs, Michael Brautbar, Jennifer Chayes and Shang-Hua Teng · 2012
Cited alongside, same era.
“Fully Dynamic Randomized Algorithms for Graph Spanners” Announced at ESA’06 and SODA’08
Surender Baswana, Sumeet Khurana and Soumojit Sarkar · 2012
Cited alongside, same era.
“Approximating the Expansion Profile and Almost Optimal Local Graph Clustering”
Shayan˜Oveis Gharan and Luca Trevisan · 2012
Cited alongside, same era.
“Matrix Concentration and Sparsification” Workshop on “Randomized Numerical Linear Algebra (RandNLA): Theory and Practice”, 2012
Nick Harvey · 2012
Cited alongside, same era.
“Improved Spectral Sparsification and Numerical Algorithms for SDD Matrices”
“An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations”
Jonathan˜A. Kelner, Yin˜Tat Lee, Lorenzo Orecchia and Aaron Sidford · 2014
Later among the works it cites.
“Simple parallel and distributed algorithms for spectral graph sparsification”
Ioannis Koutis · 2014
Later among the works it cites.
“Spanners and sparsifiers in dynamic streams”
Michael Kapralov and David˜P. Woodruff · 2014
Later among the works it cites.
“An Efficient Parallel Solver for SDD Linear Systems”
Richard Peng and Daniel˜A. Spielman · 2014
Later among the works it cites.
“Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems”
Daniel˜A. Spielman and Shang-Hua Teng · 2014
Later among the works it cites.
“Fully Dynamic Maximal Matching in O ( log n ) O(\log{n}) Update Time” Announced at FOCS’11
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Ioannis Koutis, Alex Levin and Richard Peng · 2012
Cited alongside, same era.
“Approximating the Exponential, the Lanczos Method and an O ~ ( m ) \tilde{O}(m) -Time Spectral Algorithm for Balanced Separator”
Lorenzo Orecchia, Sushant Sachdeva and Nisheeth˜K. Vishnoi · 2012
Cited alongside, same era.
“User-Friendly Tail Bounds for Sums of Random Matrices”
Joel˜A. Tropp · 2012
Cited alongside, same era.
“A Matrix Hyperbolic Cosine Algorithm and Applications”
Anastasios Zouzias · 2012
Cited alongside, same era.
“Spectral Sparsification in Dynamic Graph Streams”
Kook˜Jin Ahn, Sudipto Guha and Andrew McGregor · 2013
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.
“Fully Dynamic ( 1 + ϵ ) (1+\epsilon) -Approximate Matchings”
Manoj Gupta and Richard Peng · 2013
Cited alongside, same era.
Surender Baswana, Manoj Gupta and Sandeep Sen · 2015
Later among the works it cites.
“Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching”
Sayan Bhattacharya, Monika Henzinger and Giuseppe˜F. Italiano · 2015
Later among the works it cites.
“Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs”
Andr\’as˜A. Bencz\’ur and David˜R. Karger · 2015
Later among the works it cites.
“Efficient Sampling for Gaussian Graphical Models via Spectral Sparsification”
Dehua Cheng, Yu Cheng, Yan Liu, Richard Peng and Shang-Hua Teng · 2015
Later among the works it cites.
“Dynamic graph connectivity with improved worst case update time and sublinear space”
David Gibb, Bruce˜M. Kapron, Valerie King and Nolan Thorn · 2015
Later among the works it cites.
“Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture”
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai and Thatchaphol Saranurak · 2015
Later among the works it cites.
“Faster Spectral Sparsification of Laplacian and SDDM Matrix Polynomials”
Gorav Jindal and Pavel Kolev · 2015
Later among the works it cites.
“Sketching Cuts in Graphs and Hypergraphs”
Dmitry Kogan and Robert Krauthgamer · 2015
Later among the works it cites.
“Algorithms for Lipschitz Learning on Graphs”
Rasmus Kyng, Anup Rao, Sushant Sachdeva and Daniel˜A. Spielman · 2015
Later among the works it cites.
“Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time”
Yin˜Tat Lee and He Sun · 2015
Later among the works it cites.
“Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates”
Zeyuan˜Allen Zhu, Zhenyu Liao and Lorenzo Orecchia · 2015
Later among the works it cites.
“On Dynamic Approximate Shortest Paths for Planar Graphs with Worst-Case Costs”
Ittai Abraham, Shiri Chechik, Daniel Delling, Andrew˜V. Goldberg and Renato˜F. Werneck · 2016
Closest in time.
“Sparse Sums of Positive Semidefinite Matrices”
Marcel˜K. bSilva, Nicholas J.˜A. Harvey and Cristiane˜M. Sato · 2016
Closest in time.
“Faster Fully Dynamic Matchings with Small Approximation Ratios”
Aaron Bernstein and Cliff Stein · 2016
Closest in time.
“Sparsified Cholesky and Multigrid Solvers for Connection Laplacians”
Rasmus Kyng, Yin˜Tat Lee, Richard Peng, Sushant Sachdeva and Daniel˜A. Spielman · 2016
Closest in time.
“Approximate Undirected Maximum Flows in O ( m polylog n ) O(m\operatorname{polylog}n) Time”
Richard Peng · 2016
Closest in time.
“Dynamic ( 1 + ϵ ) (1+\epsilon) -Approximate Matchings: A Density-Sensitive Approach”
David Peleg and Shay Solomon · 2016
Closest in time.