Contraction and deletion blockers for perfect graphs and H-free graphs

dc.contributor.authorDiner, Öznur Yaşar
dc.contributor.authorPaulusma, Daniel
dc.contributor.authorPicouleau, Christophe
dc.contributor.authorRies, Bernard
dc.date.accessioned2019-06-27T08:03:32Z
dc.date.available2019-06-27T08:03:32Z
dc.date.issued2018
dc.departmentFakülteler, Mühendislik ve Doğa Bilimleri Fakültesi, Bilgisayar Mühendisliği Bölümüen_US
dc.description.abstractWe study the following problem: for given integers d k and graph G can we reduce some fixed graph parameter pi of G by at least d via at most k graph operations from some fixed set S? As parameters we take the chromatic number chi clique number omega and independence number alpha 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 pi is an element of{chi omega alpha} 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 pi is an element of{chi omega alpha} restricted to H-free graphs. (C) 2018 Elsevier B.V. All rights reserved.en_US]
dc.identifier.citation10
dc.identifier.doi10.1016/j.tcs.2018.06.023en_US
dc.identifier.endpage72
dc.identifier.issn0304-3975en_US
dc.identifier.issn1879-2294en_US
dc.identifier.issn0304-3975
dc.identifier.issn1879-2294
dc.identifier.scopus2-s2.0-85049474927en_US
dc.identifier.scopusqualityQ2
dc.identifier.startpage49en_US
dc.identifier.urihttps://hdl.handle.net/20.500.12469/804
dc.identifier.urihttps://doi.org/10.1016/j.tcs.2018.06.023
dc.identifier.volume746en_US
dc.identifier.wosWOS:000447099000005en_US
dc.identifier.wosqualityN/A
dc.institutionauthorDiner, Öznur Yaşaren_US
dc.language.isoenen_US
dc.publisherElsevier Scienceen_US
dc.relation.journalTheoretical Computer Scienceen_US
dc.relation.publicationcategoryMakale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanıen_US
dc.rightsinfo:eu-repo/semantics/openAccessen_US
dc.subjectContraction blockersen_US
dc.subjectDeletion blockersen_US
dc.subjectComplexityen_US
dc.subjectPerfect graphsen_US
dc.subjectH-free graphsen_US
dc.titleContraction and deletion blockers for perfect graphs and H-free graphsen_US
dc.typeArticleen_US
dspace.entity.typePublication

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
Contraction and deletion blockers for perfect graphs and H-free graphs.pdf
Size:
596.03 KB
Format:
Adobe Portable Document Format
Description: