COMBINATORIAL OPTIMIZATION: Packing Induced Stars in a Graph- An Extension of matching Theory Part II,   Alexander Kelmans,   University of Puerto Rico,  Mon, 16 November, 2009,   2:30 p.m. A-207


We will consider the following optimization problem.

Given a graph G, find a packing of induced stars of restricted size in G having the maximum number of vertices.

This problem is a natural generalization of the classical problem of finding in a graph a maximum matching.

We will show that all main results of matching theory can be extended to this problem. Namely, we will give a polynomial-time algorithm for solving this problem, the duality theorem, and the graph structure theorem (similar to that of Tutte-Berge duality theorem and Edmonds-Gallai structure theorem for matchings).

We will also discuss the matroid theory aspects of the above star packing problem.