A General Framework for Graph Sparsification

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

zbMATH Keywords

edge connectivitycut sparsificationedge sampling

Mathematics Subject Classification ID

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