Paper Info
Title
The labeled maximum matching problem
Abstract
Given a graph G where a label is associated with each edge, we address the problem of looking for a maximum matching of G using the minimum number of different labels, namely the labeled maximum matching problem. It is a relatively new problem whose application is related to the timetabling problem. We prove it is NP-complete and present four different mathematical formulations. Moreover, we propose an exact algorithm based on a branch-and-bound approach to solve it. We evaluate the performance of our algorithm on a wide set of instances and compare our computational times with the ones required by CPLEX to solve the proposed mathematical formulations. Test results show the effectiveness of our procedure, that hugely outperforms the solver.
Year
DOI
Venue
2009
10.1016/j.cor.2008.05.012
Computers & OR
Keywords
DocType
Volume
maximum matching problem,maximum matching,exact approach,label,new problem,different mathematical formulation,branch and bound. pacs:,proposed mathematical formulation,matching,color,branch-and-bound approach,timetabling problem,graph G,exact algorithm,different label
Journal
36
Issue
ISSN
Citations 
6
Computers and Operations Research
11
PageRank 
References 
Authors
0.56
13
3
Name
Order
Citations
PageRank
Francesco Carrabs119915.55
R. Cerulli225223.85
Monica Gentili316712.60