Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777233 | Electronic Notes in Discrete Mathematics | 2016 | 4 Pages |
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.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Rafael Veiga Pocai,