Min-Max Graph Partitioning and Small Set Expansion

DOI10.1137/120873996zbMath1360.68639arXiv1110.4319OpenAlexW2179340953MaRDI QIDQ5494941

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

Publication date: 30 July 2014

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

expansionbalanced cutspreading metricssparse cut

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (9)

Hardness and efficiency on minimizing maximum distances for graphs with few \(P_4\)'s and \((k, \ell)\)-graphs ⋮ An exact algorithm for min-max hyperstructure equipartition with a connected constraint ⋮ Parameterized algorithms for min-max multiway cut and list digraph homomorphism ⋮ \(\ell_p\)-norm multiway cut ⋮ Polynomial-time data reduction for weighted problems beyond additive goal functions ⋮ Minimum nonuniform graph partitioning with unrelated weights ⋮ Spanning Tree Congestion and Computation of Generalized Györi-Lovász Partition ⋮ Fixed parameter approximation scheme for min-max \(k\)-cut ⋮ Fixed parameter approximation scheme for min-max \(k\)-cut

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