The minimum cost perfect matching problem with conflict pair constraints


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

COMPUTERS & OPERATIONS RESEARCH, cilt.40, ss.920-930, 2013 (SCI İndekslerine Giren Dergi) identifier identifier

  • Cilt numarası: 40 Konu: 4
  • Basım Tarihi: 2013
  • Doi Numarası: 10.1016/j.cor.2012.10.022
  • Dergi Adı: COMPUTERS & OPERATIONS RESEARCH
  • Sayfa Sayıları: ss.920-930

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