|
 
|
[BCPa12] d-Transversals of Stable Sets and Vertex Covers in Weighted Bipartite Graphs
Revue Internationale avec comité de lecture : Journal Journal of Discrete Algorithms, vol. 17, pp. 95-102, 2012, (doi:10.1016/j.jda.2012.06.002)
motcle:
Résumé:
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.
Equipe:
oc
Collaboration:
LAMSADE
BibTeX
| @article { | |||
| BCPa12, | |||
| title | = | "{d-Transversals of Stable Sets and Vertex Covers in Weighted Bipartite Graphs}", | |
| author | = | "C. Bentz and M.-C. Costa and C. Picouleau and B. Ries and D. de Werra", | |
| journal | = | "Journal of Discrete Algorithms", | |
| year | = | 2012, | |
| volume | = | 17, | |
| pages | = | "95-102", | |
| doi | = | "10.1016/j.jda.2012.06.002", | |
| } | |||
