A 2k-vertex Kernel for Maximum Internal Spanning Tree Conference Paper uri icon

abstract

  • Springer International Publishing Switzerland 2015. 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 4knO(1)-time deterministic algorithm, improving all previous algorithms for the problem.

name of conference

  • Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings

published proceedings

  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

  • Li, W., Wang, J., Chen, J., & Cao, Y.

citation count

  • 15

complete list of authors

  • Li, Wenjun||Wang, Jianxin||Chen, Jianer||Cao, Yixin

publication date

  • January 2015