The maximum cardinality cut problem in co-bipartite chain graphs
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 MAXCUT) is NP-hard NP-hard in co-bipartite graphs
(Bodlaender and Jansen, Nordic J Comput 7 (2000): 14–31, 2000). We consider MaxCut
MAXCUT in co-bipartite chain graphs. We first consider the twin-free case and present an
explicit solution. We then show that MaxCut MAXCUT is polynomial time solvable in this …
in each clique can be linearly ordered with respect to inclusion. It is known that the maximum
cardinality cut problem (MaxCut MAXCUT) is NP-hard NP-hard in co-bipartite graphs
(Bodlaender and Jansen, Nordic J Comput 7 (2000): 14–31, 2000). We consider MaxCut
MAXCUT in co-bipartite chain graphs. We first consider the twin-free case and present an
explicit solution. We then show that MaxCut MAXCUT is polynomial time solvable in this …
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 () is in co-bipartite graphs (Bodlaender and Jansen, Nordic J Comput 7(2000):14–31, 2000). We consider in co-bipartite chain graphs. We first consider the twin-free case and present an explicit solution. We then show that is polynomial time solvable in this graph class.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果