|
|
 |
|
Jeudi 22 Juin
| Heure: |
10:30 - 11:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
A Polyhedral Approach to the Total Matching Problem |
| Description: |
Luca Ferrarini A total matching of a graph G = (V, E) is a subset of G such that its elements, i.e. vertices
and edges, are pairwise, not adjacent. In this context, the Total Matching Problem calls for
a total matching of maximum size. This problem generalizes both the Stable Set Problem,
where we look for a stable set of the maximum size, and the Matching Problem, where instead
we look for a matching of maximum size. In this talk, we present a polyhedral approach to
the Total Matching Problem, and hence, we introduce the corresponding polytope, namely
the Total Matching Polytope. To this end, we will present several families of nontrivial valid
inequalities which are facet-defining for the Total Matching Polytope. In addition, we provide
a first linear complete description for trees and complete bipartite graphs. For the latter
family, the complete characterization is obtained by projecting a higher-dimension polytope
onto the original space. This leads to also give an extended formulation of compact size for
the Total Matching Polytope of complete bipartite graphs. |
|
|
