Complexity of Maximum Cut on Interval Graphs
arXiv:2006.00061
Abstract
We resolve the longstanding open problem concerning the computational complexity of Max Cut on interval graphs by showing that it is NP-complete.
arXiv:2006.00061
We resolve the longstanding open problem concerning the computational complexity of Max Cut on interval graphs by showing that it is NP-complete.