Minimum Bisection is NP-hard on Unit Disk Graphs
classification
💻 cs.CC
math.CO
keywords
diskgraphsnp-hardunitbisectionemphlongstandingmin-bisection
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.