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

DOI10.1137/S009753970139567XMaRDI QIDQ5700571zbMATH OpenOpenAlexFDO

Authors Eike Seidel, Klaus Jansen, Marek Karpinski, Andrzej Lingas

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

approximation algorithmscombinatorial optimizationgraph bisectionNP-hardnessplanar graphspolynomial time approximation schemes

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1688377
• A Polylogarithmic Approximation of the Minimum Bisection
• A polynomial-time bicriteria approximation scheme for planar bisection
• Approximation Algorithms for Geometric Intersection Graphs
• Improved approximation algorithms for MAX k-cut and MAX BISECTION

Cited in

(22)

• An improved kernel for max-bisection above tight lower bound
• 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
• Balanced polychromatic 2-coloring of triangulations
• Speeding up a memetic algorithm for the max-bisection problem
• Minimum bisection is NP-hard on unit disk graphs
• Linear-programming design and analysis of fast algorithms for Max 2-CSP
• scientific article; zbMATH DE number 1688377 (Why is no real title available?)
• A polynomial-time bicriteria approximation scheme for planar bisection
• On minimum bisection and related partition problems in graphs with bounded tree width
• Approximating minimum k-section in trees with linear diameter
• Approximation Algorithms for Geometric Intersection Graphs
• Local search: is brute-force avoidable?
• Minimum bisection is fixed-parameter tractable
• A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs
• Approximation schemes for metric bisection and partitioning
• Solving cut-problems in quadratic time for graphs with bounded treewidth
• On minimum vertex bisection of random \(d\)-regular graphs
• Triangles improve 0.878 approximation for Maxcut
• An exact combinatorial algorithm for minimum graph bisection
• A bounded-error quantum polynomial-time algorithm for two graph bisection problems
• MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs

This page was built for publication: Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs

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