MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
From MaRDI portal
Publication:884483
DOI10.1016/j.tcs.2007.02.013zbMath1118.68073MaRDI QIDQ884483
Publication date: 6 June 2007
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2007.02.013
68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
Related Items
Complexity and Polynomially Solvable Special Cases of QUBO, Complexity of maximum cut on interval graphs, \textsc{max-cut} and containment relations in graphs, A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs, A bounded-error quantum polynomial-time algorithm for two graph bisection problems, The maximum cardinality cut problem in co-bipartite chain graphs, Dilation coefficient, plane-width, and resolution coefficient of graphs, An improved kernel for max-bisection above tight lower bound, A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs, On the maximum cardinality cut problem in proper interval graphs and related graph classes, Balanced polychromatic 2-coloring of triangulations, Computing the largest bond and the maximum connected cut of a graph, max-cut and Containment Relations in Graphs, Approximation Algorithms for Geometric Intersection Graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unit disk graphs
- Unit disk graph recognition is NP-hard
- Efficient graph representations
- Approximating Layout Problems on Random Geometric Graphs
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Node-and edge-deletion NP-complete problems
- Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
- Better Approximation Schemes for Disk Graphs
