A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs

作者：Boyaci Arman; Ekim Tinaz; Shalom Mordechai^*

来源：Information Processing Letters, 2017, 121: 29-33.

DOI：10.1016/j.ipl.2017.01.007

• 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.

• 出版日期2017-5