The maximum cardinality cut problem in co-bipartite chain graphs |
| |
Authors: | Arman Boyacı Tınaz Ekim Mordechai Shalom |
| |
Institution: | 1.Department of Industrial Engineering,Bogazi?i University,Istanbul,Turkey;2.TelHai College,Upper Galilee,Israel |
| |
Abstract: | 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 (\({\textsc {MaxCut}}\)) is \({\textsc {NP}}{\text {-hard}}\) in co-bipartite graphs (Bodlaender and Jansen, Nordic J Comput 7(2000):14–31, 2000). We consider \({\textsc {MaxCut}}\) in co-bipartite chain graphs. We first consider the twin-free case and present an explicit solution. We then show that \({\textsc {MaxCut}}\) is polynomial time solvable in this graph class. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|