Minimum Bisection Is NP-hard on Unit Disk Graphs

DOI10.1007/978-3-662-44465-8_22zbMath1426.68100arXiv1404.0117OpenAlexW2963515234MaRDI QIDQ2922613

George B. Mertzios, Josep Diaz

Publication date: 14 October 2014

Published in: Mathematical Foundations of Computer Science 2014 (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1404.0117

zbMATH Keywords

planar graphsNP-hardnessunit disk graphsminimum bisection problem

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (3)

An \(O(n^4)\) time algorithm to compute the bisection width of solid grid graphs ⋮ Unnamed Item ⋮ A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs

This page was built for publication: Minimum Bisection Is NP-hard on Unit Disk Graphs