The maximum cardinality cut problem in co-bipartite chain graphs
Journal of Combinatorial Optimization, cilt.35, sa.1, ss.250-265, 2018 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 35 Sayı: 1
- Basım Tarihi: 2018
- Doi Numarası: 10.1007/s10878-015-9963-x
- Dergi Adı: Journal of Combinatorial Optimization
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
- Sayfa Sayıları: ss.250-265
- Anahtar Kelimeler: Chain graph, Co-bipartite graphs, Dynamic programming, Maximum cut
- Boğaziçi Üniversitesi Adresli: Evet
Özet
A co-bipartite chain graph is a co-bipartite graph in which the neighborhoods of the vertices in each clique can be linearly ordered with respect to inclusion. It is known that the maximum cardinality cut problem (MAXCUT) is NP -hard in co-bipartite graphs (Bodlaender and Jansen, Nordic J Comput 7(2000):14–31, 2000). We consider MAXCUT in co-bipartite chain graphs. We first consider the twin-free case and present an explicit solution. We then show that MAXCUT is polynomial time solvable in this graph class.