An SDP-based algorithm for linear-sized spectral sparsification

DOI10.1145/3055399.3055477zbMath1370.05202arXiv1702.08415OpenAlexW2594480752MaRDI QIDQ4978013

He Sun, Yin Tat Lee

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

spectral graph theoryspectral sparsification

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Signed and weighted graphs (05C22)

Related Items (8)

Finding Sparse Solutions for Packing and Covering Semidefinite Programs ⋮ Minimum Cuts and Sparsification in Hypergraphs ⋮ A Spectral Approach to Network Design ⋮ Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions ⋮ Unnamed Item ⋮ Faster cut sparsification of weighted graphs ⋮ Unnamed Item ⋮ Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs

This page was built for publication: An SDP-based algorithm for linear-sized spectral sparsification