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