Show simple item record

dc.contributor.authorBentz, Cédric
HAL ID: 181270
dc.contributor.authorCosta, Marie-Christine
HAL ID: 4529
dc.contributor.authorPicouleau, Christophe
HAL ID: 181059
ORCID: 0000-0001-8092-1923
dc.contributor.authorRies, Bernard
dc.contributor.authorde Werra, Dominique
dc.date.accessioned2013-09-05T11:02:00Z
dc.date.available2013-09-05T11:02:00Z
dc.date.issued2012
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/11622
dc.language.isoenen
dc.subjectTransversalen
dc.subjectMatchingen
dc.subjectStable seten
dc.subjectVertex coveren
dc.subjectBipartite graphen
dc.subjectNetwork flowen
dc.subject.ddc511en
dc.titled-Transversals of stable sets and vertex covers in weighted bipartite graphsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenLet G=(V,E) be a graph in which every vertex v∈V has a weight w(v)⩾0 and a cost c(v)⩾0. Let SG be the family of all maximum-weight stable sets in G. For any integer d⩾0, a minimum d-transversal in the graph G with respect to SG is a subset of vertices T⊆V of minimum total cost such that |T∩S|⩾d for every S∈SG. In this paper, we present a polynomial-time algorithm to determine minimum d-transversals in bipartite graphs. Our algorithm is based on a characterization of maximum-weight stable sets in bipartite graphs. We also derive results on minimum d-transversals of minimum-weight vertex covers in weighted bipartite graphs.en
dc.relation.isversionofjnlnameJournal of Discrete Algorithms
dc.relation.isversionofjnlvol17en
dc.relation.isversionofjnldate2012
dc.relation.isversionofjnlpages95-102en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.jda.2012.06.002en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelPrincipes généraux des mathématiquesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record