Max-Cut and Max-Bisection are NP-hard on unit disk graphs

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We prove that the Max-Cut and Max-Bisection problems are NP-hard on unit disk graphs. We also show that $λ$-precision graphs are planar for $λ$ > 1 / \sqrt{2}$.

Keywords

Data Structures and Algorithms, Computational Complexity

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/116171

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/cs/0609128
 http://arxiv.org/abs/cs/0609128

Collections

arXiv