Minimum bisection is NP-hard on unit disk graphs
From MaRDI portal
Publication:2407090
DOI10.1016/j.ic.2017.04.010zbMath1376.68053OpenAlexW2609264909MaRDI QIDQ2407090
George B. Mertzios, Josep Diaz
Publication date: 28 September 2017
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: http://dro.dur.ac.uk/19737/1/19737.pdf
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 (2)
A graph theoretical approach to the firebreak locating problem ⋮ A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
Cites Work
- Unit disk graph recognition is NP-hard
- Dissemination of information in communication networks. Broadcasting, gossiping, leader election, and fault-tolerance.
- Approximating Layout Problems on Random Geometric Graphs
- An $\mathcal{O}(n^4)$ Time Algorithm to Compute the Bisection Width of Solid Grid Graphs
- An Efficient Heuristic Procedure for Partitioning Graphs
- The bisection width of grid graphs
- Exact Combinatorial Branch-and-Bound for Graph Bisection
- Minimum bisection is fixed parameter tractable
- Node-and edge-deletion NP-complete problems
- Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Minimum bisection is NP-hard on unit disk graphs
