Approximating the minimum bisection size (extended abstract)

DOI10.1145/335305.335370zbMath1296.05162OpenAlexW2005887911MaRDI QIDQ3192022

Robert Krauthgamer, Kobbi Nissim, Uriel Feige

Publication date: 26 September 2014

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

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

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (max. 100)

Bisection of bounded treewidth graphs by convolutions ⋮ A note on internal partitions: the 5-regular case and beyond ⋮ Unnamed Item ⋮ Dynamic Balanced Graph Partitioning ⋮ Minimum Bisection Is Fixed-Parameter Tractable ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On cutting a few vertices from a graph ⋮ Heuristics for semirandom graph problems

This page was built for publication: Approximating the minimum bisection size (extended abstract)