Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions

DOI10.1137/19m1247632arXiv1805.12051OpenAlexW3034963086MaRDI QIDQ6139829

Richard Peng, Saurabh Sawlani, Junxing Wang, Timothy Chu, Yu Gao, Sushant Sachdeva

Publication date: 19 December 2023

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1805.12051

zbMATH Keywords

effective resistancespectral sparsificationgraph sketchingdegree-preserving sparsifiersEulerian sparsifiersresistance sparsifiers

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Electric routing and concurrent flow cutting
• User-friendly tail bounds for sums of random matrices
• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Ramanujan graphs
• On Sketching Quadratic Forms
• Spectral sparsification via random spanners
• Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
• Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates
• Spectral Sparsification of Graphs
• Fully dynamic randomized algorithms for graph spanners
• Concentration Inequalities and Martingale Inequalities: A Survey
• The Laplacian Paradigm: Emerging Algorithms for Massive Graphs
• A Scheme for Fast Parallel Communication
• Sparsification—a technique for speeding up dynamic graph algorithms
• Approximate Undirected Maximum Flows in O(mpolylog(n)) Time
• A Framework for Analyzing Resparsification Algorithms
• Efficient $\widetilde{O}(n/\epsilon)$ Spectral Sketches for the Laplacian and its Pseudoinverse
• Cascades and Myopic Routing in Nonhomogeneous Kleinberg’s Small World Model
• Twice-Ramanujan Sparsifiers
• Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs
• An SDP-based algorithm for linear-sized spectral sparsification
• Sampling random spanning trees faster than matrix multiplication
• Dynamic spanning forest with worst-case update time: adaptive, Las Vegas, and O(n^{1/2 - ε})-time
• Spectrum Approximation Beyond Fast Matrix Multiplication: Algorithms and Hardness
• Massively Parallel Algorithms for Finding Well-Connected Components in Sparse Graphs
• Optimal Lower Bounds for Sketching Graph Cuts
• Short Cycles via Low-Diameter Decompositions
• Expander Decomposition and Pruning: Faster, Stronger, and Simpler
• An efficient parallel solver for SDD linear systems
• Towards Resistance Sparsifiers
• Sparsified Cholesky and multigrid solvers for connection laplacians
• Fast Generation of Random Spanning Trees and the Effective Resistance Metric
• An Almost-Linear-Time Algorithm for Approximate Max Flow in Undirected Graphs, and its Multicommodity Generalizations
• Computing Cut-Based Hierarchical Decompositions in Almost Linear Time
• Approaching Optimality for Solving SDD Linear Systems
• Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs
• A Nearly-m log n Time Solver for SDD Linear Systems
• Scalable Algorithms for Data and Network Analysis
• Graph Sparsification by Effective Resistances

This page was built for publication: Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions