Refine my results

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

In: Journal of Discrete Algorithms, 2012, vol. 17, p. 95-102

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...