Maximal matching polytope in trees

TURAL M. K.

OPTIMIZATION METHODS & SOFTWARE, cilt.31, sa.3, ss.471-478, 2016 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 31 Sayı: 3
  • Basım Tarihi: 2016
  • Doi Numarası: 10.1080/10556788.2015.1104679
  • Dergi Adı: OPTIMIZATION METHODS & SOFTWARE
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.471-478
  • Anahtar Kelimeler: graph theory, matching, integer programming, linear programming, polyhedral combinatorics, 90C05, 90C10, 90C57, 05C05, 05C70, EDGE DOMINATING SETS, GRAPHS, POLYHEDRON
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Ö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.