Obtaining split graphs by edge contraction
Publication in refereed journal


Times Cited
Web of Science4WOS source URL (as at 11/08/2020) Click here for the latest count
Altmetrics Information
.

Other information
AbstractWe 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(0(k2))n(5), but admits no polynomial kernel unless NP C coNP/poly. (C) 2015 Elsevier B.V. All rights reserved.
All Author(s) ListGuo CW, Cai LZ
Journal nameTheoretical Computer Science
Detailed descriptionTo ORKTS: Published on line, volume and page numbers are yet to be assigned.
Year2015
Month11
Day23
Volume Number607
PublisherElsevier
Pages60 - 67
ISSN0304-3975
eISSN1879-2294
LanguagesEnglish-United Kingdom
KeywordsEdge contraction; FPT algorithm; Incompressibility; Parameterized complexity; Split graphs
Web of Science Subject CategoriesComputer Science; Computer Science, Theory & Methods

Last updated on 2020-12-08 at 02:47