论文标题
置换图上的maxcut是NP完整的
MaxCut on Permutation Graphs is NP-complete
论文作者
论文摘要
在本文中，我们证明了最大问题在置换图上是NP完整的，这解决了David S. Johnson的1985年“正在进行的NP-Completentes”的1985年列中出现的长期开放问题。
In this paper, we prove that the MaxCut problem is NP-complete on permutation graphs, settling a long-standing open problem that appeared in the 1985 column of the "Ongoing Guide to NP-completeness" by David S. Johnson.
