学术文献库

论文标题

间隔图上最大切割的复杂性

Complexity of Maximum Cut on Interval Graphs

论文作者

Adhikary, Ranendu, Bose, Kaustav, Mukherjee, Satwik, Roy, Bodhayan

论文摘要

我们通过证明它是NP完整的，解决了关于间隔图上最大切割的计算复杂性的长期开放问题。

We resolve the longstanding open problem concerning the computational complexity of Max Cut on interval graphs by showing that it is NP-complete.