Publication details for Dr George MertziosDiaz, J. & Mertzios, G.B. (2017). Minimum bisection is NP-hard on unit disk graphs. Information and Computation 256: 83-92.
- Publication type: Journal Article
- ISSN/ISBN: 0890-5401
- DOI: 10.1016/j.ic.2017.04.010
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
In this paper we prove that the Min-Bisection problem is NP-hard on unit disk graphs, thus solving a longstanding open question.