Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/55362
Title: A 2k-vertex kernel for maximum internal spanning tree
Authors: Li, W
Wang, J
Chen, J
Cao, Y 
Keywords: Kernelization algorithms
Local-search
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
URI: http://hdl.handle.net/10397/55362
ISBN: 9783319218397
ISSN: 0302-9743
EISSN: 1611-3349
DOI: 10.1007/978-3-319-21840-3_41
Appears in Collections:Conference Paper

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

SCOPUSTM   
Citations

5
Last Week
0
Last month
Citations as of Sep 23, 2017

Page view(s)

68
Last Week
1
Last month
Checked on Sep 25, 2017

Google ScholarTM

Check

Altmetric



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