Skip to main content

Research Repository

Advanced Search

Minimum bisection is NP-hard on unit disk graphs

Diaz, J.; Mertzios, G.B.

Minimum bisection is NP-hard on unit disk graphs Thumbnail


Authors

J. Diaz



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

Files






You might also like



Downloadable Citations