Cheeger-Type Approximation for Sparsest st -Cut

DOI10.1145/2996799zbMath1446.68120arXiv1410.3889OpenAlexW1579163687MaRDI QIDQ4962650

Robert Krauthgamer, Tal Wagner

Publication date: 5 November 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

sparsest cutCheeger inequality

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (1)

Mean isoperimetry with control on outliers: exact and approximation algorithms

This page was built for publication: Cheeger-Type Approximation for Sparsest st -Cut