MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
From MaRDI portal
Publication:884483
DOI10.1016/j.tcs.2007.02.013zbMath1118.68073OpenAlexW2064530627MaRDI 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
Related Items (14)
Complexity and Polynomially Solvable Special Cases of QUBO ⋮ Computing the largest bond and the maximum connected cut of a graph ⋮ Approximation Algorithms for Geometric Intersection Graphs ⋮ Complexity of maximum cut on interval graphs ⋮ The maximum cardinality cut problem in co-bipartite chain graphs ⋮ Dilation coefficient, plane-width, and resolution coefficient of graphs ⋮ \textsc{max-cut} and containment relations in graphs ⋮ An improved kernel for max-bisection above tight lower bound ⋮ A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs ⋮ max-cut and Containment Relations in Graphs ⋮ A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs ⋮ A bounded-error quantum polynomial-time algorithm for two graph bisection problems ⋮ On the maximum cardinality cut problem in proper interval graphs and related graph classes ⋮ Balanced polychromatic 2-coloring of triangulations
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
This page was built for publication: MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
