Graph Sparsification by Effective Resistances
From MaRDI portal
Publication:6032752
DOI10.1137/080734029zbMath1237.05129OpenAlexW1983193888MaRDI QIDQ6032752
Daniel A. Spielman, Nikhil Srivastava
Publication date: 15 March 2012
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/080734029
Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random matrices (algebraic aspects) (15B52)
Related Items
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving, Efficient Point-to-Point Resistance Distance Queries in Large Graphs, Randomized numerical linear algebra: Foundations and algorithms, Graph coarsening: from scientific computing to machine learning, Rigidity of Random Subgraphs and Eigenvalues of Stiffness Matrices, Graphs, Vectors, and Matrices, Unnamed Item, Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time, Algorithmic techniques for finding resistance distances on structured graphs, Shape Simplification Through Graph Sparsification, Proportional Volume Sampling and Approximation Algorithms for A-Optimal Design, The controllability Gramian of lattice graphs, Persistent Laplacians: Properties, Algorithms and Implications, A Spectral Approach to Network Design, Data Analytics on Graphs Part I: Graphs and Spectra on Graphs, Sparsification of Binary CSPs, Unnamed Item, Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space, Constructive subsampling of finite frames with applications in optimal function recovery, Communication-efficient distributed graph clustering and sparsification under duplication models, Randomized algorithms in numerical linear algebra, Local2global: a distributed approach for scaling representation learning on graphs, Unnamed Item, Duality and nonlinear graph Laplacians, Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions, Minimum cost flow in the CONGEST model, Unnamed Item, Expander spanning subgraphs with large girth, Newton Sketch: A Near Linear-Time Optimization Algorithm with Linear-Quadratic Convergence, Determinant-Preserving Sparsification of SDDM Matrices, An effective region force for some variational models for learning and clustering, Single Pass Spectral Sparsification in Dynamic Streams, Unnamed Item, Faster cut sparsification of weighted graphs, Higher dimensional electrical circuits, A note on using the resistance-distance matrix to solve Hamiltonian cycle problem, Effective Resistance Preserving Directed Graph Symmetrization, Graph Clustering using Effective Resistance, A queueing network-based distributed Laplacian solver for directed graphs, Near-optimal discrete optimization for experimental design: a regret minimization approach, Resistance distance in straight linear 2-trees, Approximating Spectral Clustering via Sampling: A Review, Density Independent Algorithms for Sparsifying k-Step Random Walks, Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis, A primal-dual optimization strategy for elliptic partial differential equations, Engineering a combinatorial Laplacian solver: lessons learned, A queueing network-based distributed Laplacian solver, Toward a unified theory of sparse dimensionality reduction in Euclidean space, Polynomial-time algorithms for submodular Laplacian systems, On using Toeplitz and circulant matrices for Johnson-Lindenstrauss transforms, Approximate \(\ell_0\)-penalized estimation of piecewise-constant signals on graphs, Partitioning Well-Clustered Graphs: Spectral Clustering Works!, A generalized Lieb's theorem and its applications to spectrum estimates for a sum of random matrices, Unnamed Item, Unnamed Item, Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm, Unnamed Item, On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms, Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem, Several topological indices of two kinds of tetrahedral networks, Sparsification of Binary CSPs, Approximation Algorithms for D-optimal Design, Fast predictive multi-fidelity prediction with models of quantized fidelity levels, Reducing Parallel Communication in Algebraic Multigrid through Sparsification, A General Framework for Graph Sparsification, On Computationally Tractable Selection of Experiments in Measurement-Constrained Regression Models, Spanning 2-forests and resistance distance in 2-connected graphs, Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs, Electrical flows over spanning trees, Sparsification of Two-Variable Valued Constraint Satisfaction Problems, Graph Powering and Spectral Robustness, A fast algorithm for manifold learning by posing it as a symmetric diagonally dominant linear system