dc.contributor.author | Prieto, Elena | eng |
dc.contributor.author | Sloper, Christian | eng |
dc.date.accessioned | 2006-03-01T15:45:58Z | |
dc.date.available | 2006-03-01T15:45:58Z | |
dc.date.issued | 2006-02-28 | eng |
dc.Published | Theoretical Computer Science 2006 351(3): 437-445 | |
dc.identifier.issn | 0304-3975 | en_US |
dc.identifier.uri | https://hdl.handle.net/1956/1113 | |
dc.description.abstract | 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). | |
dc.format.extent | 132816 bytes | eng |
dc.format.mimetype | application/pdf | eng |
dc.language.iso | eng | eng |
dc.publisher | Elsevier | en_US |
dc.title | Looking at the Stars | en_US |
dc.type | Journal article | |
dc.description.version | acceptedVersion | en_US |
dc.identifier.doi | https://doi.org/10.1016/j.tcs.2005.10.009 | |
dc.source.journal | Theoretical Computer Science | |
dc.source.pagenumber | 437-445 | |
dc.identifier.citation | Theoretical Computer Science 2006 351(3): 437-445 | |
dc.source.volume | 351 | |
dc.source.issue | 3 | |