A 2k-vertex Kernel for Maximum Internal Spanning Tree

DOI10.1007/978-3-319-21840-3_41zbMath1451.68206arXiv1412.8296MaRDI QIDQ3449846

Yixin Cao, Jianxin Wang, Wenjun Li, Jian'er Chen

Publication date: 30 October 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1412.8296

zbMATH Keywords

local search; parameterized computation; kernelization algorithms

Mathematics Subject Classification ID

68W40: Analysis of algorithms

05C05: Trees

68R10: Graph theory (including graph drawing) in computer science

05C85: Graph algorithms (graph-theoretic aspects)

68Q27: Parameterized complexity, tractability and kernelization