MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
type: Item
instance of: scholarly article
title: MAX-CUT and MAX-BISECTION are NP-hard on unit disk graphs
zbMATH Open document ID: 1118.68073
published in: Theoretical Computer Science
publication date: 2007-06-06T00:00:00Z
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 5161900
zbMATH Keywords: computational complexity
zbMATH Keywords: Max-cut
zbMATH Keywords: Max-bisection
zbMATH Keywords: NP-hard
zbMATH Keywords: unit disk graphs
author: J. Díaz
author: Marcin Kamiński
MaRDI profile type: Publication
full work available at URL: j.tcs.2007.02.013
OpenAlex ID: W2064530627
cites work: Unit disk graph recognition is NP-hard
cites work: Q4500843
cites work: Unit disk graphs
cites work: Approximating layout problems on random geometric graphs
cites work: Q4198056
cites work: Q3328583
cites work: Finding a Maximum Cut of a Planar Graph in Polynomial Time
cites work: NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs
cites work: Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
cites work: Q4142699
cites work: Better Approximation Schemes for Disk Graphs
cites work: Q5659589
cites work: Efficient graph representations
cites work: Node-and edge-deletion NP-complete problems
DOI: 10.1016/J.TCS.2007.02.013
description: scientific article; zbMATH DE number 5161900