• English
    • Türkçe
  • English 
    • English
    • Türkçe
  • Login
View Item 
  •   DSpace Home
  • Araştırma Çıktıları / WOS
  • Araştırma Çıktıları / WOS
  • View Item
  •   DSpace Home
  • Araştırma Çıktıları / WOS
  • Araştırma Çıktıları / WOS
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

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

Thumbnail
View/Open
Contraction and deletion blockers for perfect graphs and H-free graphs.pdf (596.0Kb)
Date
2018
Author
Diner, Öznur Yaşar
Paulusma, Daniel
Picouleau, Christophe
Ries, Bernard
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.

Source

Theoretical Computer Science

Volume

746

Pages

49-72

URI

https://hdl.handle.net/20.500.12469/804
https://doi.org/10.1016/j.tcs.2018.06.023

Collections

  • Araştırma Çıktıları / Scopus [1345]
  • Araştırma Çıktıları / WOS [1335]
  • Bilgisayar Mühendisliği / Computer Engineering [183]

Keywords

Contraction blockers
Deletion blockers
Complexity
Perfect graphs
H-free graphs

Share


DSpace software copyright © 2002-2015  DuraSpace
Contact Us | Send Feedback
Theme by 
@mire NV
 

 

Browse

All of DSpaceCommunities & CollectionsBy Issue DateBy AuthorsBy TitlesBy SubjectsBy TypesBy LanguagesBy DepartmentsBy PublishersBy KHAS AuthorsBy Access TypesThis CollectionBy Issue DateBy AuthorsBy TitlesBy SubjectsBy TypesBy LanguagesBy DepartmentsBy PublishersBy KHAS AuthorsBy Access Types

My Account

LoginRegister

Statistics

View Google Analytics Statistics

DSpace software copyright © 2002-2015  DuraSpace
Contact Us | Send Feedback
Theme by 
@mire NV