Approximating the minimum bisection size (extended abstract)
From MaRDI portal
Publication:3192022
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
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
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