Thumbnail

On complexity and approximability of the Labeled maximum/perfect matching problems

Monnot, Jérôme (2005), On complexity and approximability of the Labeled maximum/perfect matching problems, in Deng, Xiaotie; Du, Ding-Zhu, Algorithms and Computation 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005, Proceedings, Springer : Berlin, p. 934-943. http://dx.doi.org/10.1007/11602613_93

View/Open
Type
Communication / Conférence
Date
2005
Conference title
16th International Symposium on Algorithms and Computation (ISAAC'05)
Conference date
2005-12
Conference city
Sanya (Hainan)
Conference country
Chine
Book title
Algorithms and Computation 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005, Proceedings
Book author
Deng, Xiaotie; Du, Ding-Zhu
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
3827
Published in
Berlin
ISBN
978-3-540-30935-2
Number of pages
1190
Pages
934-943
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 n vertices with a color (or label) function L : E→ {c1,...,cq}, the labeled maximum matching problem consists in finding a maximum matching on G that uses a minimum or a maximum number of colors.
Subjects / Keywords
labeled matching; colored matching; bipartite graphs; NP-complete; approximate algorithms