The Complexity of SIMPLE MAX-CUT on Comparability Graphs

详细信息    查看全文

• 作者：Rafael Veiga Pocai¹ ; ^{rvpocai@ime.usp.br" class="auth_mail" title="E-mail the corresponding author}
• 关键词：max-cut ; comparability graphs ; computational complexity
• 刊名：Electronic Notes in Discrete Mathematics
• 出版年：2016
• 出版时间：November 2016
• 年：2016
• 卷：55
• 期：Complete
• 页码：161-164
• 全文大小：182 K

文摘

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.