A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs
|Title||A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs|
|Publication Type||Journal Article|
|Year of Publication||2017|
|Authors||Boyacı, A., T. Ekim, and M. Shalom|
|Journal||Information Processing Letters|
|Keywords||Graph algorithms, Maximum cut, Proper interval graph|
It is known that the maximum cardinality cut problem is NP-hard even in chordal graphs. On the positive side, the problem is known to be polynomial time solvable in some subclasses of proper interval graphs which is in turn a subclass of chordal graphs. In this paper, we consider the time complexity of the problem in proper interval graphs, and propose a polynomial-time dynamic programming algorithm.