Contraction and Deletion Blockers for Perfect Graphs and H-Free Graphs
| gdc.relation.journal | Theoretical Computer Science | en_US |
| dc.contributor.author | Diner, Öznur Yaşar | |
| dc.contributor.author | Paulusma, Daniel | |
| dc.contributor.author | Picouleau, Christophe | |
| dc.contributor.author | Ries, Bernard | |
| dc.date.accessioned | 2019-06-27T08:03:32Z | |
| dc.date.available | 2019-06-27T08:03:32Z | |
| dc.date.issued | 2018 | |
| dc.description.abstract | We 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.citationcount | 10 | |
| dc.identifier.doi | 10.1016/j.tcs.2018.06.023 | en_US |
| dc.identifier.issn | 0304-3975 | en_US |
| dc.identifier.issn | 1879-2294 | en_US |
| dc.identifier.issn | 0304-3975 | |
| dc.identifier.issn | 1879-2294 | |
| dc.identifier.scopus | 2-s2.0-85049474927 | en_US |
| dc.identifier.uri | https://hdl.handle.net/20.500.12469/804 | |
| dc.identifier.uri | https://doi.org/10.1016/j.tcs.2018.06.023 | |
| dc.language.iso | en | en_US |
| dc.publisher | Elsevier Science | en_US |
| dc.relation.ispartof | Theoretical Computer Science | |
| dc.rights | info:eu-repo/semantics/openAccess | en_US |
| dc.subject | Contraction blockers | en_US |
| dc.subject | Deletion blockers | en_US |
| dc.subject | Complexity | en_US |
| dc.subject | Perfect graphs | en_US |
| dc.subject | H-free graphs | en_US |
| dc.title | Contraction and Deletion Blockers for Perfect Graphs and H-Free Graphs | en_US |
| dc.type | Article | en_US |
| dspace.entity.type | Publication | |
| gdc.author.institutional | Diner, Öznur Yaşar | en_US |
| gdc.author.institutional | Yaşar Diner, Öznur | |
| gdc.bip.impulseclass | C5 | |
| gdc.bip.influenceclass | C4 | |
| gdc.bip.popularityclass | C4 | |
| gdc.coar.access | open access | |
| gdc.coar.type | text::journal::journal article | |
| gdc.description.department | Fakülteler, Mühendislik ve Doğa Bilimleri Fakültesi, Bilgisayar Mühendisliği Bölümü | en_US |
| gdc.description.endpage | 72 | |
| gdc.description.publicationcategory | Makale - Uluslararası Hakemli Dergi - Kurum Öğretim Elemanı | en_US |
| gdc.description.scopusquality | Q2 | |
| gdc.description.startpage | 49 | en_US |
| gdc.description.volume | 746 | en_US |
| gdc.identifier.openalex | W2963080703 | |
| gdc.identifier.wos | WOS:000447099000005 | en_US |
| gdc.oaire.accesstype | HYBRID | |
| gdc.oaire.diamondjournal | false | |
| gdc.oaire.impulse | 3.0 | |
| gdc.oaire.influence | 3.6537584E-9 | |
| gdc.oaire.isgreen | true | |
| gdc.oaire.keywords | FOS: Computer and information sciences | |
| gdc.oaire.keywords | Discrete Mathematics (cs.DM) | |
| gdc.oaire.keywords | Perfect graphs | |
| gdc.oaire.keywords | 511 | |
| gdc.oaire.keywords | [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS] | |
| gdc.oaire.keywords | [INFO] Computer Science [cs] | |
| gdc.oaire.keywords | Computational Complexity (cs.CC) | |
| gdc.oaire.keywords | Contraction blockers | |
| gdc.oaire.keywords | H-free graphs | |
| gdc.oaire.keywords | Principes généraux des mathématiques | |
| gdc.oaire.keywords | Deletion blockers | |
| gdc.oaire.keywords | Computer Science - Data Structures and Algorithms | |
| gdc.oaire.keywords | FOS: Mathematics | |
| gdc.oaire.keywords | Mathematics - Combinatorics | |
| gdc.oaire.keywords | Data Structures and Algorithms (cs.DS) | |
| gdc.oaire.keywords | Complexity | |
| gdc.oaire.keywords | 004 | |
| gdc.oaire.keywords | [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO] | |
| gdc.oaire.keywords | [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM] | |
| gdc.oaire.keywords | Computer Science - Computational Complexity | |
| gdc.oaire.keywords | Combinatorics (math.CO) | |
| gdc.oaire.keywords | Computer Science - Discrete Mathematics | |
| gdc.oaire.popularity | 1.3753596E-8 | |
| gdc.oaire.publicfunded | false | |
| gdc.oaire.sciencefields | 0211 other engineering and technologies | |
| gdc.oaire.sciencefields | 0102 computer and information sciences | |
| gdc.oaire.sciencefields | 02 engineering and technology | |
| gdc.oaire.sciencefields | 01 natural sciences | |
| gdc.openalex.fwci | 1.387 | |
| gdc.openalex.normalizedpercentile | 0.83 | |
| gdc.opencitations.count | 15 | |
| gdc.plumx.crossrefcites | 13 | |
| gdc.plumx.mendeley | 5 | |
| gdc.plumx.scopuscites | 17 | |
| gdc.scopus.citedcount | 17 | |
| gdc.wos.citedcount | 13 | |
| relation.isAuthorOfPublication | 84ac79d3-823a-4abf-9b15-e1383ec8a9f5 | |
| relation.isAuthorOfPublication.latestForDiscovery | 84ac79d3-823a-4abf-9b15-e1383ec8a9f5 | |
| relation.isOrgUnitOfPublication | fd8e65fe-c3b3-4435-9682-6cccb638779c | |
| relation.isOrgUnitOfPublication | 2457b9b3-3a3f-4c17-8674-7f874f030d96 | |
| relation.isOrgUnitOfPublication | b20623fc-1264-4244-9847-a4729ca7508c | |
| relation.isOrgUnitOfPublication.latestForDiscovery | fd8e65fe-c3b3-4435-9682-6cccb638779c |
Files
Original bundle
1 - 1 of 1
Loading...
- Name:
- Contraction and deletion blockers for perfect graphs and H-free graphs.pdf
- Size:
- 596.03 KB
- Format:
- Adobe Portable Document Format
- Description: