Article ID Journal Published Year Pages File Type
5777233 Electronic Notes in Discrete Mathematics 2016 4 Pages PDF
Abstract
We adapt a result by Masuda et al. [IEEE Transactions on Computers 39 (1990), 124-127] on FIXED LINEAR CROSSING NUMBER to show that SIMPLE MAX-CUT is NP-hard on comparability graphs.
Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Preview
The Complexity of SIMPLE MAX-CUT on Comparability Graphs
Authors
,