d-Transversals of Stable Sets and Vertex Covers in Weighted Bipartite Graphs

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.
Type de document :
Article dans une revue
Journal of Discrete Algorithms, Elsevier, 2012, 17, pp.95-102. 〈10.1016/j.jda.2012.06.002〉
Liste complète des métadonnées

https://hal-ensta.archives-ouvertes.fr/hal-00969156
Contributeur : Aurélien Arnoux <>
Soumis le : mercredi 2 avril 2014 - 10:44:27
Dernière modification le : jeudi 24 mai 2018 - 15:58:08

Lien texte intégral

Identifiants

Collections

Citation

Cédric Bentz, Marie-Christine Costa, Christophe Picouleau, Bernard Ries, Dominique De Werra. d-Transversals of Stable Sets and Vertex Covers in Weighted Bipartite Graphs. Journal of Discrete Algorithms, Elsevier, 2012, 17, pp.95-102. 〈10.1016/j.jda.2012.06.002〉. 〈hal-00969156〉

Partager

Métriques

Consultations de la notice

183