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érenceDate
2011Conference title
EuroComb 2011Conference date
2011-08Conference city
BudapestConference country
HongrieJournal name
Electronic Notes in Discrete MathematicsVolume
38Publisher
Elsevier
Publication identifier
Metadata
Show full item recordAuthor(s)
Bentz, CédricCosta, Marie-Christine
de Werra, Dominique
Picouleau, Christophe

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; TransversalsRelated items
Showing items related by title and author.
-
Bentz, Cédric; Costa, Marie-Christine; Picouleau, Christophe; Ries, Bernard; de Werra, Dominique (2012) Article accepté pour publication ou publié
-
Bentz, Cédric; Costa, Marie-Christine; de Werra, Dominique; Picouleau, Christophe; Ries, Bernard; Zenklusen, R. (2009) Communication / Conférence
-
Ries, Bernard; Picouleau, Christophe; de Werra, Dominique; Costa, Marie-Christine; Bentz, Cédric (2011) Chapitre d'ouvrage
-
Bentz, Cédric; Costa, Marie-Christine; Ries, Bernard; de Werra, Dominique; Picouleau, Christophe; Zenklusen, Rico (2010) Article accepté pour publication ou publié
-
Bernard Ries; Picouleau, Christophe; de Werra, Dominique; Costa, Marie-Christine; Bentz, Cédric (2009) Article accepté pour publication ou publié