Seminar
COMBINATORIAL OPTIMIZATION: Packing Induced Stars in a Graph- An Extension of matching Theory, Alexander Kelmans, University of Puerto Rico, Mon, 9 November, 2009, 2:30 p.m. A-207
Abstract
We will consider the following optimization problem.
Given a graph G, ï¬nd 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 ï¬nding 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.