Approximating the minimum bisection size (extended abstract)

DOI10.1145/335305.335370MaRDI QIDQ3192022zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• scientific article; zbMATH DE number 1929926
• Approximating minimum cut with bounded size
• On minimum bisection and related partition problems in graphs with bounded tree width
• scientific article; zbMATH DE number 2086657
• Minimum bisection is fixed-parameter tractable
• An exact combinatorial algorithm for minimum graph bisection
• A Polylogarithmic Approximation of the Minimum Bisection
• A polylogarithmic approximation of the minimum bisection
• scientific article; zbMATH DE number 2140434
• A 2-approximation for the maximum satisfying bisection problem

Cited in

(29)

• Finding good approximate vertex and edge partitions is NP-hard
• Heuristics for semirandom graph problems
• On cutting a few vertices from a graph
• Minimum transversals of maximum matchings as approximate solutions to the bisection problem
• Bisection of bounded treewidth graphs by convolutions
• A polylogarithmic approximation of the minimum bisection
• Minimum bisection is NP-hard on unit disk graphs
• On the maximal error of spectral approximation of graph bisection
• Vertex Bisection is Hard, too
• On the graph bisection problem
• scientific article; zbMATH DE number 666305 (Why is no real title available?)
• Minimum bisection is fixed-parameter tractable
• scientific article; zbMATH DE number 1929926 (Why is no real title available?)
• Brief announcement: Bounded-degree cut is fixed-parameter tractable
• Bisection of bounded treewidth graphs by convolutions
• New abilities and limitations of spectral graph bisection
• Dynamic balanced graph partitioning
• Bisections above Tight Lower Bounds
• A 2-approximation for the maximum satisfying bisection problem
• An efficient algorithm for graph bisection of triangularizations
• A Polylogarithmic Approximation of the Minimum Bisection
• Ruling Out PTAS for Graph Min‐Bisection, Dense k‐Subgraph, and Bipartite Clique
• A note on internal partitions: the 5-regular case and beyond
• A parameterized approximation scheme for min \(k\)-cut
• A subquadratic bound for online bisection
• Improved bounds for online balanced graph re-partitioning
• On the minimum edge bisection of graph
• Contraction decomposition in unit disk graphs and algorithmic applications in parameterized complexity
• A bounded-error quantum polynomial-time algorithm for two graph bisection problems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3192022)