A Polylogarithmic Approximation of the Minimum Bisection

DOI10.1137/050640904zbMath1088.05068OpenAlexW2069985946MaRDI QIDQ5470837

Robert Krauthgamer, Uriel Feige

Publication date: 1 June 2006

Published in: SIAM Review (Search for Journal in Brave)

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

zbMATH Keywords

partitionalgorithmgraph partitioningdivide and conquer

Mathematics Subject Classification ID

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

Related Items (13)

A deterministic annealing algorithm for approximating a solution of the min-bisection problem ⋮ Bounds on the max and min bisection of random cubic and random 4-regular graphs ⋮ From the quantum approximate optimization algorithm to a quantum alternating operator ansatz ⋮ Fission: Practical algorithms for computing minimum balanced node separators ⋮ A deterministic annealing algorithm for the minimum concave cost network flow problem ⋮ Dynamic Balanced Graph Partitioning ⋮ Competitive clustering of stochastic communication patterns on a ring ⋮ Partition-based logical reasoning for first-order and propositional theories ⋮ Community Detection and Stochastic Block Models ⋮ Unbalanced graph cuts with minimum capacity ⋮ On cutting a few vertices from a graph ⋮ Improved analysis of online balanced clustering ⋮ Continuum limit of total variation on point clouds

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