The minimum cost perfect matching problem with conflict pair constraints

ÖNCAN T., Zhang R., Punnen A. P.

COMPUTERS & OPERATIONS RESEARCH, cilt.40, sa.4, ss.920-930, 2013 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 40 Sayı: 4
  • Basım Tarihi: 2013
  • Doi Numarası: 10.1016/j.cor.2012.10.022
  • Dergi Adı: COMPUTERS & OPERATIONS RESEARCH
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.920-930
  • Galatasaray Üniversitesi Adresli: Evet

Özet

In this paper we address the minimum cost perfect matching problem with conflict pair constraints (MCPMPC). Given an undirected graph G with a cost associated with each edge and a conflict set of pairs of edges, the MCPMPC is to find a perfect matching with the lowest total cost such that no more than one edge is selected from each pair in the conflict set. MCPMPC is known to be strongly NP-hard. We present additional complexity results and identify new polynomially solvable cases for the general MCPMPC. Several heuristic algorithms and lower bounding schemes are presented. The proposed algorithms are tested on randomly generated instances. Encouraging experimental results are also reported. (C) 2012 Elsevier Ltd. All rights reserved.