点击次数：

所属单位：计算机科学与技术学院/人工智能学院/软件学院

发表刊物：Inf. Process. Lett.

摘要：The problem of modifying a given graph to satisfy certain properties has been one of the central topics in parameterized tractability study. In this paper, we investigate the cycle contraction problem, which makes a graph into a cycle by edge contractions. The problem was raised by Belmonte et al. [IPEC 2013] and they obtained a linear kernel with at most 6k+6 vertices for it. We provide an improved kernel with at most 5k+4 vertices for the problem in this paper. Our result showcases how to design kernelization algorithm for one problem by exploiting kernels of another problem. © 2019 Elsevier B.V.

ISSN号：0020-0190

是否译文：否

发表时间：2019-09-01

合写作者：Sun, Yuefang

通讯作者：盛斌