.png){kind=icon}
.png){kind=icon}
Return
The labeled maximum matching problem
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2008.05.012.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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. (C) 2008 Elsevier Ltd. All rights reserved.
Keywords:
Matching
Label
Color
Exact approach
Branch and bound
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W