2004 | OriginalPaper | Buchkapitel
Looking at the Stars
verfasst von : Elena Prieto, Christian Sloper
Erschienen in: Parameterized and Exact Computation
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 prove that packing k copies of H = K1, s is fixed-parameter tractable and give a quadratic kernel for the general case. 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 ${\mathcal O}^*(2^{5.3k})$.