Turkish Journal of Mathematics and Computer Science

Turkish Journal of Mathematics and Computer Science

A Maximum Cardinality Cut Algorithm for Co-bipartite and Split Graphs Using Bimodular Decomposition

Yazarlar: Arman BOYACI, Mordechai SHALOM

Cilt 13 , Sayı 1 , 2021 , Sayfalar 182 - 191

Konular:Matematik

DOI:10.47000/tjmcs.748563

Anahtar Kelimeler:Maximum cardinality cut,Bimodular decomposition,Split graphs.

Özet: 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.

ATIFLAR
Atıf Yapan Eserler
Henüz Atıf Yapılmamıştır
KAYNAK GÖSTER
BibTex
KOPYALA
@article{2021, title={A Maximum Cardinality Cut Algorithm for Co-bipartite and Split Graphs Using Bimodular Decomposition}, volume={13}, number={182–191}, publisher={Turkish Journal of Mathematics and Computer Science}, author={Arman BOYACI,Mordechai SHALOM}, year={2021} }
APA
KOPYALA
Arman BOYACI,Mordechai SHALOM. (2021). A Maximum Cardinality Cut Algorithm for Co-bipartite and Split Graphs Using Bimodular Decomposition (Vol. 13). Vol. 13. Turkish Journal of Mathematics and Computer Science.
MLA
KOPYALA
Arman BOYACI,Mordechai SHALOM. A Maximum Cardinality Cut Algorithm for Co-Bipartite and Split Graphs Using Bimodular Decomposition. no. 182–191, Turkish Journal of Mathematics and Computer Science, 2021.
Atıf Görüntüle
PDF Görüntüle
Kaynak Görüntüle
Paylaş
Dergi Bilgileri