A General Framework for Graph Sparsification
From MaRDI portal
Publication:5232324
DOI10.1137/16M1091666zbMath1430.68204OpenAlexW2958706771MaRDI QIDQ5232324
Nicholas J. A. Harvey, Ramesh Hariharan, Wai Shing Fung, Debmalya Panigrahi
Publication date: 2 September 2019
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/16m1091666
Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Connectivity (05C40) Randomized algorithms (68W20) Signed and weighted graphs (05C22)
Related Items (3)
Quantum Speedup for Graph Sparsification, Cut Approximation, and Laplacian Solving ⋮ Faster cut sparsification of weighted graphs ⋮ Learning to sparsify travelling salesman problem instances
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- User-friendly tail bounds for sums of random matrices
- A linear-time algorithm for finding a sparse \(k\)-connected spanning subgraph of a \(k\)-connected graph
- Probabilistic methods for algorithmic discrete mathematics
- Random Sampling in Cut, Flow, and Network Design Problems
- On Sketching Quadratic Forms
- Spectral sparsification via random spanners
- A Matrix Hyperbolic Cosine Algorithm and Applications
- Subgraph sparsification and nearly optimal ultrasparsifiers
- Spectral Sparsification and Regret Minimization Beyond Matrix Multiplicative Updates
- Spectral Sparsification of Graphs
- Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
- Graph Sparsification in the Semi-streaming Model
- Graph spanners
- Computing Edge-Connectivity in Multigraphs and Capacitated Graphs
- A Reduction Method for Edge-Connectivity in Graphs
- A new approach to the minimum cut problem
- Twice-ramanujan sparsifiers
- Randomized Approximation Schemes for Cuts and Flows in Capacitated Graphs
- A general framework for graph sparsification
- A Nearly-m log n Time Solver for SDD Linear Systems
- Edge Disjoint Paths in Moderately Connected Graphs
- Graph Sparsification by Effective Resistances
This page was built for publication: A General Framework for Graph Sparsification
