Subgraph sparsification and nearly optimal ultrasparsifiers

DOI10.1145/1806689.1806699zbMath1293.05370OpenAlexW2014255080MaRDI QIDQ2875132

Alexandra Kolla, Yury Makarychev, Amin Saberi, Shang-Hua Teng

Publication date: 13 August 2014

Published in: Proceedings of the forty-second ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1806689.1806699

zbMATH Keywords

approximation algorithmsalgebraic connectivitygraph sparsificationultrasparsifiers

Mathematics Subject Classification ID

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

Related Items (7)

A Local Search Framework for Experimental Design ⋮ A Spectral Approach to Network Design ⋮ Unnamed Item ⋮ Advances in metric embedding theory ⋮ Extracting a basis with fixed block inside a matrix ⋮ A General Framework for Graph Sparsification ⋮ An approximation algorithm for the maximum spectral subgraph problem

This page was built for publication: Subgraph sparsification and nearly optimal ultrasparsifiers