d-Transversals of Stable Sets and Vertex Covers in Weighted Bipartite Graphs
2012
Publication type:
Paper in peer-reviewed journals
Journal:
Journal of Discrete Algorithms, vol. 17, pp. 95--102
HAL:
Abstract:
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.
BibTeX:
@article{Ben-Cos-Pic-Rie-DeW-2012, author={Cédric Bentz and Marie-Christine Costa and Christophe Picouleau and Bernard Ries and Dominique de Werra }, title={d-Transversals of Stable Sets and Vertex Covers in Weighted Bipartite Graphs }, doi={10.1016/j.jda.2012.06.002 }, journal={Journal of Discrete Algorithms }, year={2012 }, volume={17 }, pages={95--102}, }