MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
We prove that the MAX-CUT and MAX-BISECTION problems are NP-hard on unit disk graphs. We also show that X-precision aphs are planar for lambda > 1/root 2- and give a dichotomy theorem for MAX-CUT computational complexity on X-precision unit disk graphs. (c) 2007 Elsevier B.V. All rights reserved.
max-cut max-bisection np-hard unit disk graphs computational complexity