Title of article
Minimum d-Transversals of Maximum-Weight Stable Sets in Trees
Author/Authors
Bentz، نويسنده , , Cédric and Costa، نويسنده , , Marie-Christine and de Werra، نويسنده , , Dominique and Picouleau، نويسنده , , Christophe and Ries، نويسنده , , Bernard، نويسنده ,
Issue Information
روزنامه با شماره پیاپی سال 2011
Pages
6
From page
129
To page
134
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
trees , Transversals , Maximum-weight stable sets
Journal title
Electronic Notes in Discrete Mathematics
Serial Year
2011
Journal title
Electronic Notes in Discrete Mathematics
Record number
1455782
Link To Document