| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 435668 | Theoretical Computer Science | 2015 | 14 Pages |
Abstract
Two restricted versions of the Subforest Isomorphism problem, the Covering a Tree by a Set of Stars (CTSS) and the Covering a Tree by a Set of Paths (CTSP) problems, are studied. Both problems are NP-complete. The problems are closely related to a number of well-studied problems, including the problems Subgraph Isomorphism, Tree Editing, and Graph Packing. It is shown that the problems CTSS and CTSP are fixed-parameter tractable. Thorough development of parameterized algorithms and kernelization algorithms for these problems are presented.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jie You, Jianxin Wang, Qilong Feng, Feng Shi,