Advertisement
Published in:
2005 | OriginalPaper | Chapter
On Complexity and Approximability of the Labeled Maximum/Perfect Matching Problems
Author : Jérôme Monnot
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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
n
vertices with a color (or label) function
L
:
E
→ {
c
1
,...,
c
q
}, the labeled maximum matching problem consists in finding a maximum matching on
G
that uses a minimum or a maximum number of colors.