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

Simple item page
dc.creatorDiaz, Josep
dc.creatorKaminski, Marcin
dc.date2006-09-22
dc.date.accessioned2026-07-07T07:23:57Z
dc.date.available2026-07-07T07:23:57Z
dc.descriptionWe 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}$.
dc.identifierhttps://arxiv.org/abs/cs/0609128
dc.identifierhttp://arxiv.org/abs/cs/0609128
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/116171
dc.subjectData Structures and Algorithms
dc.subjectComputational Complexity
dc.titleMax-Cut and Max-Bisection are NP-hard on unit disk graphs
dc.typetext

Files

Collections

arXiv