• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

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 (2012), d-Transversals of stable sets and vertex covers in weighted bipartite graphs, Journal of Discrete Algorithms, 17, p. 95-102. http://dx.doi.org/10.1016/j.jda.2012.06.002

Type
Article accepté pour publication ou publié
Date
2012
Journal name
Journal of Discrete Algorithms
Volume
17
Publisher
Elsevier
Pages
95-102
Publication identifier
http://dx.doi.org/10.1016/j.jda.2012.06.002
Metadata
Show full item record
Author(s)
Bentz, Cédric
Costa, Marie-Christine
Picouleau, Christophe cc
Ries, Bernard
de Werra, Dominique
Abstract (EN)
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.
Subjects / Keywords
Transversal; Matching; Stable set; Vertex cover; Bipartite graph; Network flow

Related items

Showing items related by title and author.

  • Thumbnail
    Minimum d-Transversals of Maximum-Weight Stable Sets in Trees 
    Bentz, Cédric; Costa, Marie-Christine; de Werra, Dominique; Picouleau, Christophe; Ries, Bernard (2011) Communication / Conférence
  • Thumbnail
    Weighted Transversals and Blockers for Some Optimization Problems in Graphs 
    Ries, Bernard; Picouleau, Christophe; de Werra, Dominique; Costa, Marie-Christine; Bentz, Cédric (2011) Chapitre d'ouvrage
  • Thumbnail
    Blockers and transversalsnext term in some previous termsubclasses of bipartite graphs: When caterpillars are dancing on a gridnext term 
    Bentz, Cédric; Costa, Marie-Christine; Ries, Bernard; de Werra, Dominique; Picouleau, Christophe; Zenklusen, Rico (2010) Article accepté pour publication ou publié
  • Thumbnail
    d-bloqueurs et d-transversaux 
    Bentz, Cédric; Costa, Marie-Christine; de Werra, Dominique; Picouleau, Christophe; Ries, Bernard; Zenklusen, R. (2009) Communication / Conférence
  • Thumbnail
    Degree-constrained edge partitionings in graphs arising from discrete tomography 
    Bernard Ries; Picouleau, Christophe; de Werra, Dominique; Costa, Marie-Christine; Bentz, Cédric (2009) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo