MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
From MaRDI portal
Publication:884483
DOI10.1016/J.TCS.2007.02.013zbMATH Open1118.68073OpenAlexW2064530627MaRDI QIDQ884483FDOQ884483
Authors: J. Díaz, Marcin Kamiński 
Publication date: 6 June 2007
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2007.02.013
Recommendations
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Unit disk graphs
- Unit disk graph recognition is NP-hard
- Efficient graph representations
- Node-and edge-deletion NP-complete problems
- Title not available (Why is that?)
- Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
- NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
- Approximating layout problems on random geometric graphs
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- Better Approximation Schemes for Disk Graphs
- Title not available (Why is that?)
Cited In (22)
- Computing the largest bond and the maximum connected cut of a graph
- Complexity of maximum cut on interval graphs
- Title not available (Why is that?)
- An improved kernel for max-bisection above tight lower bound
- Contact graphs of boxes with unidirectional contacts
- Complexity and polynomially solvable special cases of QUBO
- \textsc{max-cut} and containment relations in graphs
- Max-Cut and containment relations in graphs
- A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
- Complexity of the weighted max-cut in Euclidean space
- A bounded-error quantum polynomial-time algorithm for two graph bisection problems
- Minimum bisection is NP-hard on unit disk graphs
- Approximation Algorithms for Geometric Intersection Graphs
- NP-hardness of the Euclidean Max-Cut problem
- Minimum bisection is NP-hard on unit disk graphs
- Canonical cuts of path powers
- Balanced polychromatic 2-coloring of triangulations
- On the maximum cardinality cut problem in proper interval graphs and related graph classes
- Dilation coefficient, plane-width, and resolution coefficient of graphs
- The maximum cardinality cut problem in co-bipartite chain graphs
- A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs
- The complexity of SIMPLE MAX-CUT on comparability graphs
This page was built for publication: MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q884483)
