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

Cédric Bentz 1, 2 Marie-Christine Costa 3, 1 Christophe Picouleau 1 Bernard Ries 4 Dominique de Werra 3, 4
1 CEDRIC - Centre d'études et de recherche en informatique et communications
2 LRI - Laboratoire de Recherche en Informatique
3 OC - Optimisation et commande
4 Département de Mathématiques - EPFL
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.
Document type :
Journal articles
Complete list of metadatas
https://hal-ensta-paris.archives-ouvertes.fr//hal-00969156
Contributor : Aurélien Arnoux <>
Submitted on : Wednesday, April 2, 2014 - 10:44:27 AM
Last modification on : Wednesday, July 3, 2019 - 10:48:04 AM

Links full text

openaccess

Identifiers

Collections

ENSTA | UMA_ENSTA | UMR8623 | INRIA | UNIV-HESAM | CEDRIC-CNAM

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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

230

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD