Bentz, Cédric Costa, Marie-Christine Picouleau, Christophe Ries, Bernard de Werra, Dominique 2012 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. application/pdf https://folia.unifr.ch/global/documents/308009 https://folia.unifr.ch/documents/308009/files/transversals.pdf eng info:eu-repo/semantics/altIdentifier/doi/10.1016/j.jda.2012.06.002 info:eu-repo/semantics/openAccess License undefined Journal of Discrete Algorithms. - Elsevier. - 2012, vol. 17, p. 95-102 Theoretical Computer Science Computational Theory and Mathematics Discrete Mathematics and Combinatorics info:eu-repo/classification/udc/004 d-Transversals of stable sets and vertex covers in weighted bipartite graphs http://purl.org/coar/resource_type/c_6501