• 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 Blockers for Graphs with Forbidden Induced Paths

Thumbnail
View/Open
Contraction Blockers for Graphs.pdf (405.2Kb)
Date
2015
Author
Diner, Öznur Yaşar
Paulusma, Daniel
Picouleau, Christophe
Ries, Bernard
Abstract
We consider the following problem: can a certain graph parameter of some given graph be reduced by at least d for some integer d via at most k edge contractions for some given integer k? We examine three graph parameters: the chromatic number clique number and independence number. For each of these graph parameters we show that when d is part of the input this problem is polynomial-time solvable on P-4-free graphs and NP-complete as well as W[1]-hard with parameter d for split graphs. As split graphs form a subclass of P-5-free graphs both results together give a complete complexity classification for P-l-free graphs. The W[1]-hardness result implies that it is unlikely that the problem is fixed-parameter tractable for split graphs with parameter d. But we do show on the positive side that the problem is polynomial-time solvable for each parameter on split graphs if d is fixed i.e. not part of the input. We also initiate a study into other subclasses of perfect graphs namely cobipartite graphs and interval graphs.

Source

Algorithms and Complexity (CIAC 2015)

Volume

9079

Pages

194-207

URI

https://hdl.handle.net/20.500.12469/647
https://dx.doi.org/10.1007/978-3-319-18173-8_14

Collections

  • Araştırma Çıktıları / Scopus [1565]
  • Araştırma Çıktıları / WOS [1518]
  • Bilgisayar Mühendisliği / Computer Engineering [188]

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