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

Diaz, J. & Mertzios, G.B. (2017). Minimum bisection is NP-hard on unit disk graphs. Information and Computation 256: 83-92.

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.