d-Transversals of stable sets and vertex covers in weighted bipartite graphs
Bentz, Cédric; Costa, Marie-Christine; Picouleau, Christophe; Ries, Bernard; de Werra, Dominique (2012), d-Transversals of stable sets and vertex covers in weighted bipartite graphs, Journal of Discrete Algorithms, 17, p. 95-102. http://dx.doi.org/10.1016/j.jda.2012.06.002
Type
Article accepté pour publication ou publiéDate
2012Journal name
Journal of Discrete AlgorithmsVolume
17Publisher
Elsevier
Pages
95-102
Publication identifier
Metadata
Show full item recordAuthor(s)
Bentz, CédricCosta, Marie-Christine
Picouleau, Christophe

Ries, Bernard
de Werra, Dominique
Abstract (EN)
Let 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.Subjects / Keywords
Transversal; Matching; Stable set; Vertex cover; Bipartite graph; Network flowRelated items
Showing items related by title and author.
-
Bentz, Cédric; Costa, Marie-Christine; de Werra, Dominique; Picouleau, Christophe; Ries, Bernard (2011) Communication / Conférence
-
Ries, Bernard; Picouleau, Christophe; de Werra, Dominique; Costa, Marie-Christine; Bentz, Cédric (2011) Chapitre d'ouvrage
-
Bentz, Cédric; Costa, Marie-Christine; Ries, Bernard; de Werra, Dominique; Picouleau, Christophe; Zenklusen, Rico (2010) Article accepté pour publication ou publié
-
Bentz, Cédric; Costa, Marie-Christine; de Werra, Dominique; Picouleau, Christophe; Ries, Bernard; Zenklusen, R. (2009) Communication / Conférence
-
Bernard Ries; Picouleau, Christophe; de Werra, Dominique; Costa, Marie-Christine; Bentz, Cédric (2009) Article accepté pour publication ou publié