We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham University

Computer Science


Publication details for Dr George Mertzios

Díaz, J. & Mertzios, G.B. (2014). Minimum Bisection Is NP-hard on Unit Disk Graphs. In Mathematical Foundations of Computer Science 2014: 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II. Csuhaj-Varjú, Erzsébet Dietzfelbinger, Martin & Ésik, Zoltán Berlin, Heidelberg: Springer. 8635: 251-262.

Author(s) from Durham


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