The superstar packing problem

Autor: Marek Janata, Jácint Szabó
Rok vydání: 2009
Předmět:
Zdroj: Combinatorica. 29:27-48
ISSN: 1439-6912
0209-9683
DOI: 10.1007/s00493-009-1986-4
Popis: Hell and Kirkpatrick proved that in an undirected graph, a maximum size packing by a set of non-singleton stars can be found in polynomial time if this star-set is of the form {S 1, S 2, ..., S k } for some k∈ℤ+ (S i is the star with i leaves), and it is NP-hard otherwise. This may raise the question whether it is possible to enlarge a set of stars not of the form {S 1, S 2, ..., S k } by other non-star graphs to get a polynomially solvable graph packing problem. This paper shows such families of depth 2 trees. We show two approaches to this problem, a polynomial alternating forest algorithm, which implies a Berge-Tutte type min-max theorem, and a reduction to the degree constrained subgraph problem of Lovasz.
Databáze: OpenAIRE
Externí odkaz: