Spectral Sparsification of Graphs
From MaRDI portal
Publication:3096091
DOI10.1137/08074489XzbMath1228.68040OpenAlexW2129575457WikidataQ56386818 ScholiaQ56386818MaRDI QIDQ3096091
Daniel A. Spielman, Shang-Hua Teng
Publication date: 7 November 2011
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/08074489x
Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)
Related Items (58)
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Graph coarsening: from scientific computing to machine learning ⋮ A Unified Framework for Structured Graph Learning via Spectral Constraints ⋮ Graphs, Vectors, and Matrices ⋮ Bounds on the spectral sparsification of symmetric and off-diagonal nonnegative real matrices ⋮ Unnamed Item ⋮ Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time ⋮ Shape Simplification Through Graph Sparsification ⋮ Spectral sparsification in the semi-streaming setting ⋮ A Spectral Approach to Network Design ⋮ Sparsification of Binary CSPs ⋮ Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space ⋮ Communication-efficient distributed graph clustering and sparsification under duplication models ⋮ A combinatorial cut-toggling algorithm for solving Laplacian linear systems ⋮ Comparison of matrix norm sparsification ⋮ Better hardness results for the minimum spanning tree congestion problem ⋮ Prediction models with graph kernel regularization for network data ⋮ The resistance perturbation distance: a metric for the analysis of dynamic networks ⋮ Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Rumor Spreading with No Dependence on Conductance ⋮ Nodal domain count for the generalized graph \(p\)-Laplacian ⋮ Interactions of computational complexity theory and mathematics ⋮ Network Essence: PageRank Completion and Centrality-Conforming Markov Chains ⋮ Determinant-Preserving Sparsification of SDDM Matrices ⋮ Single Pass Spectral Sparsification in Dynamic Streams ⋮ Mixing in High-Dimensional Expanders ⋮ Faster cut sparsification of weighted graphs ⋮ Vertex Sparsification in Trees ⋮ Drawing Big Graphs Using Spectral Sparsification ⋮ Graph Clustering using Effective Resistance ⋮ The weighted barycenter drawing recognition problem ⋮ Approximating Spectral Clustering via Sampling: A Review ⋮ An Adaptive Fast Solver for a General Class of Positive Definite Matrices Via Energy Decomposition ⋮ Unnamed Item ⋮ Partitioning Well-Clustered Graphs: Spectral Clustering Works! ⋮ Ranking and Sparsifying a Connection Graph ⋮ A generalized Lieb's theorem and its applications to spectrum estimates for a sum of random matrices ⋮ A spectral approach to the shortest path problem ⋮ Nonlinear network dynamics with consensus-dissensus bifurcation ⋮ Unnamed Item ⋮ Information graph flow: a geometric approximation of quantum and statistical systems ⋮ Stein's method for stationary distributions of Markov chains and application to Ising models ⋮ Refined Vertex Sparsifiers of Planar Graphs ⋮ Improved Guarantees for Vertex Sparsification in Planar Graphs ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Sparsification of Binary CSPs ⋮ Toward a spectral theory of cellular sheaves ⋮ A distributed algorithm for spectral sparsification of graphs with applications to data clustering ⋮ A General Framework for Graph Sparsification ⋮ Effective resistance is more than distance: Laplacians, simplices and the Schur complement ⋮ Better streaming algorithms for the maximum coverage problem ⋮ Unnamed Item ⋮ Electrical flows over spanning trees ⋮ Sparsification of Two-Variable Valued Constraint Satisfaction Problems ⋮ A fast algorithm for manifold learning by posing it as a symmetric diagonally dominant linear system
This page was built for publication: Spectral Sparsification of Graphs
