Vis enkel innførsel

dc.contributor.authorPrieto, Elenaeng
dc.contributor.authorSloper, Christianeng
dc.date.accessioned2006-03-01T15:45:58Z
dc.date.available2006-03-01T15:45:58Z
dc.date.issued2006-02-28eng
dc.PublishedTheoretical Computer Science 2006 351(3): 437-445
dc.identifier.issn0304-3975en_US
dc.identifier.urihttps://hdl.handle.net/1956/1113
dc.description.abstractThe 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.extent132816 byteseng
dc.format.mimetypeapplication/pdfeng
dc.language.isoengeng
dc.publisherElsevieren_US
dc.titleLooking at the Starsen_US
dc.typeJournal article
dc.description.versionacceptedVersionen_US
dc.identifier.doihttps://doi.org/10.1016/j.tcs.2005.10.009
dc.source.journalTheoretical Computer Science
dc.source.pagenumber437-445
dc.identifier.citationTheoretical Computer Science 2006 351(3): 437-445
dc.source.volume351
dc.source.issue3


Tilhørende fil(er)

Thumbnail

Denne innførselen finnes i følgende samling(er)

Vis enkel innførsel