Date
2011
Indexation documentaire
Principes généraux des mathématiques
Subject
Trees; Maximum-weight stable sets; Transversals
Nom de la revue
Electronic Notes in Discrete Mathematics
Volume
38
Nom de l'éditeur
Elsevier
Titre du colloque
EuroComb 2011
Date du colloque
08-2011
Ville du colloque
Budapest
Pays du colloque
Hongrie
Auteur
Bentz, Cédric
Costa, Marie-Christine
de Werra, Dominique
Picouleau, Christophe
Ries, Bernard
Type
Communication / Conférence
Résumé en anglais
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.
