5 citations · 12 across the 8 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2022
Maximum Cut on Interval Graphs of Interval Count Two is NP-complete
Alexey Barsukov, Bodhayan Roy
An interval graph has interval count if it has an interval model, where among every intervals there are two that have the same length. Maximum Cut on interval graph…
cs.CC2020★ 2 cited
Complexity of Maximum Cut on Interval Graphs
Ranendu Adhikary, Kaustav Bose, Satwik Mukherjee +1
We resolve the longstanding open problem concerning the computational complexity of Max Cut on interval graphs by showing that it is NP-complete.