Please use this identifier to cite or link to this item:
Title: A 2k-vertex kernel for maximum internal spanning tree
Authors: Li, W
Wang, J
Chen, J
Cao, Y 
Keywords: Kernelization algorithms
Parameterized computation
Issue Date: 2015
Publisher: Springer
Source: Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and lecture notes in bioinformatics), 2015, v. 9214, p. 495-505 How to cite?
Journal: Lecture notes in computer science (including subseries Lecture notes in artificial intelligence and lecture notes in bioinformatics) 
Abstract: We consider the parameterized version of the maximum internal spanning tree problem: given an n-vertex graph and a parameter k, does the graph have a spanning tree with at least k internal vertices? Fomin et al. [J. Comput. System Sci., 79:1-6] crafted a very ingenious reduction rule, and showed that a simple application of this rule is sufficient to yield a 3k-vertex kernel for this problem. Here we propose a novel way to use the same reduction rule, resulting in an improved 2k-vertex kernel. Our algorithm applies first a greedy procedure consisting of a sequence of local exchange operations, which ends with a local-optimal spanning tree, and then uses this special tree to find a reducible structure. As a corollary of our kernel, we obtain a 4k·nO(1)-time deterministic algorithm, improving all previous algorithms for the problem.
Description: 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015
ISBN: 9783319218397
ISSN: 0302-9743
EISSN: 1611-3349
DOI: 10.1007/978-3-319-21840-3_41
Appears in Collections:Conference Paper

View full-text via PolyU eLinks SFX Query
Show full item record


Last Week
Last month
Citations as of Sep 23, 2017

Page view(s)

Last Week
Last month
Checked on Sep 25, 2017

Google ScholarTM



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.