| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 10331265 | Information Processing Letters | 2005 | 8 Pages |
Abstract
In this paper, we deal with both the complexity and the approximability of the labeled perfect matching problem in bipartite graphs. Given a simple graph G=(V,E) with |V|=2n vertices such that E contains a perfect matching (of size n), together with a color (or label) function L:Eâ{c1,â¦,cq}, the labeled perfect matching problem consists in finding a perfect matching on G that uses a minimum or a maximum number of colors.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Jérôme Monnot,