- Title
- Looking at the stars
- Creator
- Prieto, Elena; Sloper, Christian
- Relation
- Theoretical Computer Science Vol. 351, Issue 3, p. 437-445
- Publisher Link
- http://dx.doi.org/10.1016/j.tcs.2005.10.009
- Publisher
- Elsevier
- Resource Type
- journal article
- Date
- 2006
- Description
- 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=K₁,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(2⁵‧³⁰¹ᵏk²‧⁵+n³).
- Subject
- fixed parameter algorithms; crown reduction
- Identifier
- http://hdl.handle.net/1959.13/926736
- Identifier
- uon:9925
- Identifier
- ISSN:0304-3975
- Language
- eng
- Reviewed
- Hits: 1409
- Visitors: 1356
- Downloads: 0
Thumbnail | File | Description | Size | Format |
---|