Skip to main content

Research Repository

Advanced Search

Minimum Bisection Is NP-hard on Unit Disk Graphs

Díaz, J.; Mertzios, G.B.

Minimum Bisection Is NP-hard on Unit Disk Graphs Thumbnail


Authors

J. Díaz



Contributors

Erzsébet Csuhaj-Varjú
Editor

Martin Dietzfelbinger
Editor

Zoltán Ésik
Editor

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

Díaz, J., & Mertzios, G. (2014). Minimum Bisection Is NP-hard on Unit Disk Graphs. In E. Csuhaj-Varjú, M. Dietzfelbinger, & Z. Ésik (Eds.), Mathematical foundations of computer science 2014 : 39th international symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, part II (251-262). Springer Verlag. https://doi.org/10.1007/978-3-662-44465-8_22

Publication Date 2014
Deposit Date Sep 8, 2014
Publicly Available Date Mar 29, 2024
Publisher Springer Verlag
Pages 251-262
Series Title Lecture notes in computer science
Book Title Mathematical foundations of computer science 2014 : 39th international symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, part II.
ISBN 9783662444641
DOI https://doi.org/10.1007/978-3-662-44465-8_22
Keywords Minimum bisection problem, Unit disk graphs, Planar graphs, NP-hardness.
Related Public URLs http://link.springer.com/chapter/10.1007%2F978-3-662-44465-8_22

Files





You might also like



Downloadable Citations