On the maximum cardinality cut problem in proper interval graphs and related graph classes

Basit Öğe Kaydı
dc.authorid0000-0002-2688-5703
dc.authorid0000-0002-2688-5703en_US
dc.contributor.authorBoyacı, Armanen_US
dc.contributor.authorEkim, Tınazen_US
dc.contributor.authorShalom, Mordechaien_US
dc.date.accessioned2021-11-25T00:17:58Z
dc.date.available2021-11-25T00:17:58Z
dc.date.issued2022-01-04
dc.departmentIşık Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümüen_US
dc.departmentIşık University, Faculty of Engineering, Department of Computer Engineeringen_US
dc.description.abstractAlthough it has been claimed in two different papers that the maximum cardinality cut problem is polynomial-time solvable for proper interval graphs, both of them turned out to be erroneous. In this work we consider the parameterized complexity of this problem. We show that the maximum cardinality cut problem in proper/unit interval graphs is FPT when parameterized by the maximum number of non-empty bubbles in a column of its bubble model. We then generalize this result to a more general graph class by defining new parameters related to the well-known clique-width parameter. Specifically, we define an (?,?,?)-clique-width decomposition of a graph as a clique-width decomposition in which at each step the following invariant is preserved: after discarding at most ? labels, a) every label consists of at most ? sets of twin vertices, and b) all the labels together induce a graph with independence number at most ?. We show that for every two constants ?,?>0 the problem is FPT when parameterized by ? plus the smallest width of an (?,?,?)-clique-width decomposition.en_US
dc.description.versionPublisher's Versionen_US
dc.identifier.citationBoyacı, A., Ekim, T. & Shalom, M. (2021). On the maximum cardinality cut problem in proper interval graphs and related graph classes. Theoretical Computer Science, 898, 20-29. doi:10.1016/j.tcs.2021.10.014en_US
dc.identifier.doi10.1016/j.tcs.2021.10.014
dc.identifier.endpage29
dc.identifier.issn0304-3975en_US
dc.identifier.issn1879-2294en_US
dc.identifier.scopus2-s2.0-85118880326en_US
dc.identifier.scopusqualityQ2en_US
dc.identifier.startpage20
dc.identifier.urihttps://hdl.handle.net/11729/3306
dc.identifier.urihttp://dx.doi.org/10.1016/j.tcs.2021.10.014
dc.identifier.volume898
dc.identifier.wosWOS:000722885600002en_US
dc.identifier.wosqualityQ4
dc.identifier.wosqualityQ4en_US
dc.indekslendigikaynakWeb of Scienceen_US
dc.indekslendigikaynakScopusen_US
dc.indekslendigikaynakScience Citation Index Expanded (SCI-EXPANDED)en_US
dc.institutionauthorShalom, Mordechaien_US
dc.language.isoenen_US
dc.peerreviewedYesen_US
dc.publicationstatusPublisheden_US
dc.publisherElsevier B.V.en_US
dc.relation.ispartofTheoretical Computer Scienceen_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/closedAccessen_US
dc.subjectBubble modelen_US
dc.subjectBubble modelsen_US
dc.subjectCardinalitiesen_US
dc.subjectClique-decompositionen_US
dc.subjectClique decompositionen_US
dc.subjectClique-widthen_US
dc.subjectGraph classen_US
dc.subjectGraph theoryen_US
dc.subjectMaximum cuten_US
dc.subjectMaximum cutsen_US
dc.subjectParameterizeden_US
dc.subjectParameterizationen_US
dc.subjectParameterized complexityen_US
dc.subjectPolynomial approximationen_US
dc.subjectPolynomial-timeen_US
dc.subjectProper interval graphen_US
dc.subjectProper interval graphsen_US
dc.subjectMax-cuten_US
dc.titleOn the maximum cardinality cut problem in proper interval graphs and related graph classesen_US
dc.typeArticleen_US

Dosyalar

Orijinal paket
Listeleniyor 1 - 1 / 1
Küçük Resim Yok
İsim:
11729-3306.pdf
Boyut:
393.4 KB
Biçim:
Adobe Portable Document Format
Açıklama:
Publisher's Version
İndir
Lisans paketi
Listeleniyor 1 - 1 / 1
Küçük Resim Yok
İsim:
license.txt
Boyut:
1.44 KB
Biçim:
Item-specific license agreed upon to submission
Açıklama:
İndir

Koleksiyon

MF - Makale Koleksiyonu | Bilgisayar Mühendisliği Bölümü / Department of Computer Engineering
Scopus İndeksli Yayınlar Koleksiyonu
WoS İndeksli Yayınlar Koleksiyonu