Show simple item record

dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.date.accessioned2010-01-14T15:26:23Z
dc.date.available2010-01-14T15:26:23Z
dc.date.issued2005
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2949
dc.language.isoenen
dc.subjectLabeled matchingen
dc.subjectApproximate algorithmsen
dc.subjectNP-completeen
dc.subjectBipartite graphsen
dc.subject.ddc003en
dc.titleThe Labeled perfect matching in bipartite graphsen
dc.typeArticle accepté pour publication ou publié
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 |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.
dc.relation.isversionofjnlnameInformation Processing Letters
dc.relation.isversionofjnlvol96en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate2005
dc.relation.isversionofjnlpages81-88en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.ipl.2005.06.009en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record