A Polylogarithmic Approximation of the Minimum Bisection

DOI10.1137/S0097539701387660zbMath1015.68240OpenAlexW2129027842MaRDI QIDQ2784494

Robert Krauthgamer, Uriel Feige

Publication date: 23 April 2002

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

Full work available at URL: https://doi.org/10.1137/s0097539701387660

zbMATH Keywords

dynamic programminggraph partitioningapproximation algorithmsdivide and conquergraph separators

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (22)

Linear kernels for separating a graph into components of bounded size ⋮ Solving the minimum bisection problem using a biologically inspired computational model ⋮ Upper bounds on the bisection width of 3- and 4-regular graphs ⋮ Bisection of bounded treewidth graphs by convolutions ⋮ Impact of minimum-cut density-balanced partitioning solutions in distributed webpage ranking ⋮ On the minimum bisection of random 3-regular graphs ⋮ 3D geo-graphs: efficient flip verification for the spherical zoning problem ⋮ Unnamed Item ⋮ Dynamic Balanced Graph Partitioning ⋮ Graph clustering ⋮ Competitive clustering of stochastic communication patterns on a ring ⋮ A semidefinite programming approach to the hypergraph minimum bisection problem ⋮ Minimum Bisection Is Fixed-Parameter Tractable ⋮ Distributed balanced partitioning via linear embedding ⋮ Unnamed Item ⋮ Techniques from combinatorial approximation algorithms yield efficient algorithms for random 2\(k\)-SAT ⋮ Inoculation strategies for victims of viruses and the sum-of-squares partition problem ⋮ Unnamed Item ⋮ On the complexity of finding balanced oneway cuts ⋮ Exact recovery in the Ising blockmodel ⋮ Balanced cut approximation in random geometric graphs ⋮ Optimizing streaming graph partitioning via a heuristic greedy method and caching strategy

This page was built for publication: A Polylogarithmic Approximation of the Minimum Bisection