d-Transversals of stable sets and vertex covers in weighted bipartite graphs

Let G=(V,E)G=(V,E) be a graph in which every vertex v∈Vv∈V has a weight w(v)⩾0w(v)⩾0 and a cost c(v)⩾0c(v)⩾0. Let SGSG be the family of all maximum-weight stable sets in G . For any integer d⩾0d⩾0, a minimum d-transversal in the graph G with respect to SGSG is a subset of vertices T⊆VT⊆V of minimum total cost such that |T∩S|⩾d|T∩S|⩾d for every S∈SGS∈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.


Published in:
Journal of Discrete Algorithms, 17, 95-102
Year:
2012
ISSN:
1570-8667
Keywords:
Laboratories:




 Record created 2014-01-20, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)