New Exact and Approximation Algorithms for the Star Packing Problem in Undirected Graphs

Maxim Babenko & Alexey Gusakov
By a T-star we mean a complete bipartite graph K_{1,t} for some t <= T. For an undirected graph G, a T-star packing is a collection of node-disjoint T-stars in G. For example, we get ordinary matchings for $T = 1$ and packings of paths of length 1 and 2 for $T = 2$. Hereinafter we assume that T >= 2. Hell and Kirkpatrick devised an ad-hoc augmenting algorithm that finds a T-star packing covering...