Show simple item record

dc.contributor.authorDiner, Öznur Yaşar
dc.contributor.authorPaulusma, Daniël
dc.contributor.authorPicouleau, Christophe
dc.contributor.authorRies, Bernard
dc.date.accessioned2020-05-22T14:28:48Z
dc.date.available2020-05-22T14:28:48Z
dc.date.issued2018
dc.identifier.issn0304-3975
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20768
dc.language.isoenen
dc.subjectContraction blockersen
dc.subjectDeletion blockersen
dc.subjectComplexityen
dc.subjectPerfect graphsen
dc.subjectH-free graphsen
dc.subject.ddc511en
dc.titleContraction and deletion blockers for perfect graphs and H-free graphsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe study the following problem: for given integers d, k and graph G, can we reduce some fixed graph parameter π of G by at least d via at most k graph operations from some fixed set S? As parameters we take the chromatic number χ, clique number ω and independence number α, and as operations we choose edge contraction ec and vertex deletion vd. We determine the complexity of this problem for S = {ec} and S = {vd} and π ∈ {χ, ω, α} for a number of subclasses of perfect graphs. We use these results to determine the complexity of the problem for S = {ec} and S = {vd} and π ∈ {χ, ω, α} restricted to H-free graphs.en
dc.relation.isversionofjnlnameTheoretical Computer Science
dc.relation.isversionofjnlvol746en
dc.relation.isversionofjnldate2018-10
dc.relation.isversionofjnlpages49-72en
dc.relation.isversionofdoi10.1016/j.tcs.2018.06.023en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2020-05-22T14:08:33Z
hal.person.labIds
hal.person.labIds
hal.person.labIds
hal.person.labIds989


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record