Maximal matching polytope in trees


TURAL M. K.

OPTIMIZATION METHODS & SOFTWARE, cilt.31, ss.471-478, 2016 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 31 Konu: 3
  • Basım Tarihi: 2016
  • Doi Numarası: 10.1080/10556788.2015.1104679
  • Dergi Adı: OPTIMIZATION METHODS & SOFTWARE
  • Sayfa Sayıları: ss.471-478

Özet

Given a weighted simple graph, the minimum weighted maximal matching (MWMM) problem is the problem of finding a maximal matching of minimum weight. The MWMM problem is NP-hard in general, but is polynomial-time solvable in some special classes of graphs. For instance, it has been shown that the MWMM problem can be solved in linear time in trees when all the edge weights are equal to one. In this paper, we show that the convex hull of the incidence vectors of maximal matchings (the maximal matching polytope) in trees is given by the polytope described by the linear programming relaxation of a recently proposed integer programming formulation. This establishes the polynomial-time solvability of the MWMM problem in weighted trees. The question of whether or not the MWMM problem can be solved in linear time in weighted trees is open.