The minimum cost perfect matching problem with conflict pair constraints

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

COMPUTERS & OPERATIONS RESEARCH, vol.40, no.4, pp.920-930, 2013 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 40 Issue: 4
  • Publication Date: 2013
  • Doi Number: 10.1016/j.cor.2012.10.022
  • Journal Name: COMPUTERS & OPERATIONS RESEARCH
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.920-930
  • Galatasaray University Affiliated: Yes

Abstract

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.