The minimum cost perfect matching problem with conflict pair constraints

Temel Öncan; Ruonan Zhang; Abraham P. Punnen

doi:10.1016/j.cor.2012.10.022

The minimum cost perfect matching problem with conflict pair constraints

Temel Öncan, Ruonan Zhang^*, Abraham P. Punnen

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

33 Citations (Scopus)

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.

Original language	English
Pages (from-to)	920-930
Number of pages	11
Journal	Computers and Operations Research
Volume	40
Issue number	4
DOIs	https://doi.org/10.1016/j.cor.2012.10.022
Publication status	Published - Apr 2013
Externally published	Yes

Keywords

Assignment problem
Conflict graph
Conflict pairs
Matching problem

Access to Document

10.1016/j.cor.2012.10.022

Cite this

@article{7bb9c76dfe624250a014c236644f987f,

title = "The minimum cost perfect matching problem with conflict pair constraints",

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.",

keywords = "Assignment problem, Conflict graph, Conflict pairs, Matching problem",

author = "Temel {\"O}ncan and Ruonan Zhang and Punnen, {Abraham P.}",

note = "Funding Information: The first author acknowledges the partial support by the Turkish Scientific and Technological Research Council (T{\"U}BİTAK) Research Grant nos. 107M462 and 109M139 . This work was partially supported by an NSERC discovery grant awarded to Abraham P. Punnen. We are thankful to the referees for their helpful comments which improved the presentation of the paper.",

year = "2013",

month = apr,

doi = "10.1016/j.cor.2012.10.022",

language = "English",

volume = "40",

pages = "920--930",

journal = "Computers and Operations Research",

issn = "0305-0548",

number = "4",

}

TY - JOUR

T1 - The minimum cost perfect matching problem with conflict pair constraints

AU - Öncan, Temel

AU - Zhang, Ruonan

AU - Punnen, Abraham P.

N1 - Funding Information: The first author acknowledges the partial support by the Turkish Scientific and Technological Research Council (TÜBİTAK) Research Grant nos. 107M462 and 109M139 . This work was partially supported by an NSERC discovery grant awarded to Abraham P. Punnen. We are thankful to the referees for their helpful comments which improved the presentation of the paper.

PY - 2013/4

Y1 - 2013/4

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

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

KW - Assignment problem

KW - Conflict graph

KW - Conflict pairs

KW - Matching problem

UR - http://www.scopus.com/inward/record.url?scp=84870866546&partnerID=8YFLogxK

U2 - 10.1016/j.cor.2012.10.022

DO - 10.1016/j.cor.2012.10.022

M3 - Article

AN - SCOPUS:84870866546

SN - 0305-0548

VL - 40

SP - 920

EP - 930

JO - Computers and Operations Research

JF - Computers and Operations Research

IS - 4

ER -

The minimum cost perfect matching problem with conflict pair constraints

Abstract

Keywords

Access to Document

Other files and links

Cite this