University of Puerto Rico    (787) 764 0000

    Seminar Abstract

    Seminar

    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

    Abstract

    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.

    Skip to content