Min-max Graph Partitioning and Small Set Expansion

DOI10.1109/FOCS.2011.79MaRDI QIDQ5495004zbMATH OpenFDO

Authors N. Bansal, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph (Seffi) Naor, Roy Schwartz, Uriel Feige

Publication date 30 July 2014

Published in 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/FOCS.2011.79

Mathematics Subject Classification ID

Signed and weighted graphs (05C22) Graph theory (including graph drawing) in computer science (68R10)

Cited in

(8)

• Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications
• Approximation algorithms for the weighted t-uniform sparsest cut and some other graph partitioning problems
• On the advantage of overlapping clusters for minimizing conductance
• Graph Clustering using Effective Resistance
• Approximation Algorithms for CSPs
• Approximating unique games using low diameter graph decomposition
• Compact oblivious routing
• Minimum congestion mapping in a cloud

This page was built for publication: Min-max Graph Partitioning and Small Set Expansion

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5495004)