• 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

Minimum d-Transversals of Maximum-Weight Stable Sets in Trees

Bentz, Cédric; Costa, Marie-Christine; de Werra, Dominique; Picouleau, Christophe; Ries, Bernard (2011), Minimum d-Transversals of Maximum-Weight Stable Sets in Trees, EuroComb 2011, 2011-08, Budapest, Hongrie

Type
Communication / Conférence
Date
2011
Conference title
EuroComb 2011
Conference date
2011-08
Conference city
Budapest
Conference country
Hongrie
Journal name
Electronic Notes in Discrete Mathematics
Volume
38
Publisher
Elsevier
Publication identifier
http://dx.doi.org/10.1016/j.endm.2011.09.022
Metadata
Show full item record
Author(s)
Bentz, Cédric
Costa, Marie-Christine
de Werra, Dominique
Picouleau, Christophe cc
Ries, Bernard
Abstract (EN)
Given an integer d and a weighted tree T, we show how to find in polynomial time a minimum d-transversal of all maximum-weight stable sets in T, i.e., a set of vertices of minimum size having at least d vertices in common with every maximum-weight stable set. Our proof relies on new structural results for maximum-weight stable sets on trees.
Subjects / Keywords
Trees; Maximum-weight stable sets; Transversals

Related items

Showing items related by title and author.

  • Thumbnail
    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) 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
    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
    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