Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950824 | Information Processing Letters | 2017 | 5 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Arman Boyacı, Tinaz Ekim, Mordechai Shalom,