Minimum bisection is NP-hard on unit disk graphs

Diaz, J.; Mertzios, G.B.

Abstract

In this paper we prove that the Min-Bisection problem is NP-hard on unit disk graphs, thus solving a longstanding open question.

Citation

Diaz, J., & Mertzios, G. (2017). Minimum bisection is NP-hard on unit disk graphs. Information and Computation, 256, 83-92. https://doi.org/10.1016/j.ic.2017.04.010

• Journal Article Type: Article
• Acceptance Date: Sep 8, 2016
• Online Publication Date: Apr 28, 2017
• Publication Date: Apr 28, 2017
• Deposit Date: Sep 12, 2016
• Publicly Available Date: Apr 28, 2018
• Journal: Information and Computation
• Print ISSN: 0890-5401
• Electronic ISSN: 1090-2651
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 256
• Pages: 83-92
• DOI: https://doi.org/10.1016/j.ic.2017.04.010
• Public URL: https://durham-repository.worktribe.com/output/1405110