| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 6423820 | Electronic Notes in Discrete Mathematics | 2011 | 6 Pages |
Abstract
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Cédric Bentz, Marie-Christine Costa, Dominique de Werra, Christophe Picouleau, Bernard Ries,