Autor:	Leizhen Cai, Chengwei Guo
Rok vydání:	2015
Předmět:	Combinatorics Discrete mathematics General Computer Science Chordal graph Polynomial kernel Edge contraction Parameterized complexity Split graph Graph Theoretical Computer Science Mathematics
Zdroj:	Theoretical Computer Science. 607:60-67
ISSN:	0304-3975
DOI:	10.1016/j.tcs.2015.01.056
Popis:	We study the parameterized complexity of the following Split Contraction problem: Given a graph G, and an integer k as parameter, determine whether G can be modified into a split graph by contracting at most k edges. We show that Split Contraction can be solved in FPT time 2 O ( k 2 ) n 5 , but admits no polynomial kernel unless NP ? coNP / poly .
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::48941cd6e6e9768488155f38c47bb19c https://doi.org/10.1016/j.tcs.2015.01.056 Zobrazit plný text záznamu Full Text from ScienceDirect