Show simple item record

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.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.issn0304-3975
dc.identifier.issn1879-2294
dc.identifier.otherWOS:000722885600002
dc.identifier.urihttps://hdl.handle.net/11729/3306
dc.identifier.urihttp://dx.doi.org/10.1016/j.tcs.2021.10.014
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.language.isoengen_US
dc.publisherElsevier B.V.en_US
dc.relation.isversionof10.1016/j.tcs.2021.10.014
dc.rightsinfo:eu-repo/semantics/openAccessen_US
dc.rightsAttribution-NonCommercial-NoDerivs 3.0 United States*
dc.rights.urihttp://creativecommons.org/licenses/by-nc-nd/3.0/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
dc.description.versionPublisher's Versionen_US
dc.relation.journalTheoretical Computer Scienceen_US
dc.contributor.departmentIşık Üniversitesi, Mühendislik Fakültesi, Bilgisayar Mühendisliği Bölümüen_US
dc.contributor.departmentIşık University, Faculty of Engineering, Department of Computer Engineeringen_US
dc.contributor.authorID0000-0002-2688-5703
dc.identifier.volume898
dc.identifier.startpage20
dc.identifier.endpage29
dc.peerreviewedYesen_US
dc.publicationstatusPublisheden_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.contributor.institutionauthorShalom, Mordechaien_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record

info:eu-repo/semantics/openAccess
Except where otherwise noted, this item's license is described as info:eu-repo/semantics/openAccess