A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs
Information Processing Letters, cilt.121, ss.29-33, 2017 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 121
- Basım Tarihi: 2017
- Doi Numarası: 10.1016/j.ipl.2017.01.007
- Dergi Adı: Information Processing Letters
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Sayfa Sayıları: ss.29-33
- Anahtar Kelimeler: Graph algorithms, Maximum cut, Proper interval graph
- Boğaziçi Üniversitesi Adresli: Evet
Özet
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.