Graph partitioning using single commodity flows

DOI10.1145/1132516.1132574zbMath1301.68205OpenAlexW2145701440MaRDI QIDQ5891927

Satish B. Rao, Rohit Khandekar, Umesh V. Vazirani

Publication date: 25 November 2014

Published in: Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

spectral methodedge-separatorsingle commodity max-flowsparse cut

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Deterministic network models in operations research (90B10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

On the advantage of overlapping clusters for minimizing conductance ⋮ Algorithmic Extensions of Cheeger’s Inequality to Higher Eigenvalues and Partitions