Thumbnail

The Labeled perfect matching in bipartite graphs

Monnot, Jérôme (2005), The Labeled perfect matching in bipartite graphs, Information Processing Letters, 96, 3, p. 81-88. http://dx.doi.org/10.1016/j.ipl.2005.06.009

View/Open
Type
Article accepté pour publication ou publié
Date
2005
Journal name
Information Processing Letters
Volume
96
Number
3
Publisher
Elsevier
Pages
81-88
Publication identifier
Metadata
Show full item record
Author(s)
Monnot, Jérôme cc
Abstract (EN)
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.
Subjects / Keywords
Labeled matching; Approximate algorithms; NP-complete; Bipartite graphs