Minimum Bisection Is NP-hard on Unit Disk Graphs

Díaz, 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

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: Sep 17, 2014
• 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.
• Public URL: https://durham-repository.worktribe.com/output/1677761
• Related Public URLs: http://link.springer.com/chapter/10.1007%2F978-3-662-44465-8_22