Looking at the Stars
Journal article
Accepted version

View/ Open
Date
2006-02-28Metadata
Show full item recordCollections
- Department of Informatics [1002]
Original version
Theoretical Computer Science 2006 351(3): 437-445 https://doi.org/10.1016/j.tcs.2005.10.009Abstract
The problem of packing k vertex-disjoint copies of a graph H into another graph G is NP-complete if H has more than two vertices in some connected component. In the framework of parameterized complexity we analyze a particular family of instances of this problem, namely the packing of stars. We give a quadratic kernel for packing k copies of H = K1,s. When we consider the special case of s = 2, i.e., H being a star with two leaves, we give a linear kernel and an algorithm running in time O(25.301kk2.5 + n3).