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

doi:10.1016/j.jda.2012.06.002

Back

Journal article

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

Bentz, Cédric Université Paris-Sud, France
Costa, Marie-Christine ENSTA Paris-Tech, France
Picouleau, Christophe CNAM, France
Ries, Bernard Université Paris-Dauphine, France
de Werra, Dominique Ecole Polytechnique Fédérale de Lausanne, Switzerland

2012

Published in:

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

Theoretical Computer Science

Computational Theory and Mathematics

Discrete Mathematics and Combinatorics

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

Faculty

Faculté des sciences économiques et sociales et du management

Department

Département d'informatique

Language