Show simple item record

dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.date.accessioned2011-03-24T14:44:06Z
dc.date.available2011-03-24T14:44:06Z
dc.date.issued2005
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5821
dc.language.isoenen
dc.subjectlabeled matchingen
dc.subjectcolored matchingen
dc.subjectbipartite graphsen
dc.subjectNP-completeen
dc.subjectapproximate algorithmsen
dc.subject.ddc003en
dc.titleOn complexity and approximability of the Labeled maximum/perfect matching problemsen
dc.typeCommunication / Conférence
dc.description.abstractenIn 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.en
dc.identifier.citationpages934-943en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber3827
dc.relation.ispartoftitleAlgorithms and Computation 16th International Symposium, ISAAC 2005, Sanya, Hainan, China, December 19-21, 2005, Proceedingsen
dc.relation.ispartofeditorDeng, Xiaotie
dc.relation.ispartofeditorDu, Ding-Zhu
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2005
dc.relation.ispartofpages1190en
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/11602613en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-540-30935-2en
dc.relation.conftitle16th International Symposium on Algorithms and Computation (ISAAC'05)en
dc.relation.confdate2005-12
dc.relation.confcitySanya (Hainan)en
dc.relation.confcountryChineen
dc.identifier.doihttp://dx.doi.org/10.1007/11602613_93


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record