MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs

DOI10.1016/J.TCS.2007.02.013MaRDI QIDQ884483zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

computational complexityNP-hardunit disk graphsMax-bisectionMax-cut

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• Minimum bisection is NP-hard on unit disk graphs
• Unit disk graph recognition is NP-hard
• NP-hardness of the Euclidean Max-Cut problem
• Unit disk graphs
• The complexity of SIMPLE MAX-CUT on comparability graphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1496855 (Why is no real title available?)
• scientific article; zbMATH DE number 3390827 (Why is no real title available?)
• Approximating layout problems on random geometric graphs
• Better Approximation Schemes for Disk Graphs
• Efficient graph representations
• Finding a Maximum Cut of a Planar Graph in Polynomial Time
• NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
• Node-and edge-deletion NP-complete problems
• Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
• Unit disk graph recognition is NP-hard
• Unit disk graphs

Cited in

(22)

• Computing the largest bond and the maximum connected cut of a graph
• Complexity of maximum cut on interval graphs
• An improved kernel for max-bisection above tight lower bound
• scientific article; zbMATH DE number 7724211 (Why is no real title available?)
• Contact graphs of boxes with unidirectional contacts
• \textsc{max-cut} and containment relations in graphs
• Complexity and polynomially solvable special cases of QUBO
• Max-Cut and containment relations in graphs
• A (probably) optimal algorithm for \textsc{bisection} on bounded-treewidth graphs
• A bounded-error quantum polynomial-time algorithm for two graph bisection problems
• Complexity of the weighted max-cut in Euclidean space
• Minimum bisection is NP-hard on unit disk graphs
• NP-hardness of the Euclidean Max-Cut problem
• Approximation Algorithms for Geometric Intersection Graphs
• 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)