Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs

DOI10.1137/S009753970139567XzbMath1087.90063OpenAlexW2088647669MaRDI QIDQ5700571

Eike Seidel, Klaus Jansen, Andrzej Lingas, Marek Karpinski

Publication date: 28 October 2005

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

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

zbMATH Keywords

combinatorial optimizationplanar graphsgraph bisectionapproximation algorithmsNP-hardnesspolynomial time approximation schemes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

On minimum bisection and related partition problems in graphs with bounded tree width, Approximating minimum \(k\)-section in trees with linear diameter, Minimum bisection is NP-hard on unit disk graphs, MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs, Solving cut-problems in quadratic time for graphs with bounded treewidth, Approximation Algorithms for Geometric Intersection Graphs, Linear-programming design and analysis of fast algorithms for Max 2-CSP, Local search: is brute-force avoidable?, Minimum Bisection Is Fixed-Parameter Tractable, An improved kernel for max-bisection above tight lower bound, Unnamed Item, A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs, A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs, An exact combinatorial algorithm for minimum graph bisection, A bounded-error quantum polynomial-time algorithm for two graph bisection problems, Balanced polychromatic 2-coloring of triangulations, Speeding up a memetic algorithm for the max-bisection problem