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 Mar 29, 2024
Journal Information and Computation
Print ISSN 0890-5401
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 256
Pages 83-92
DOI https://doi.org/10.1016/j.ic.2017.04.010

Files





You might also like



Downloadable Citations