The maximum cardinality cut (MaxCut) problem remains NP-complete for co-bipartite graphs and
for split graphs. Based on modular decomposition, in [3] it is shown that MaxCut is polynomial-time solvable for graphs that are factorable to bounded treewidth graphs. However, this approach fails in co-bipartite graphs because the modules of a co-bipartite graph are exactly twins and connected components. In this work we extend the result of [3] to co-bipartite graphs using the concept of bimodules and bimodular decomposition proposed in [6]. Namely, we show thatMaxCut is polynomial-time solvable for co-bipartite graphs that can be factored to bounded treewidth graphs using bimodular decomposition.
Maximum cardinality cut bimodular decomposition split graphs.
Birincil Dil | İngilizce |
---|---|
Konular | Matematik |
Bölüm | Makaleler |
Yazarlar | |
Yayımlanma Tarihi | 30 Haziran 2021 |
Yayımlandığı Sayı | Yıl 2021 |