Minimum Bisection is NP-hard on Unit Disk Graphs

Josep Diaz, George B. Mertzios

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

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment