research article
Minimum d-Transversals of Maximum-Weight Stable Sets in Trees
December 1, 2011
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. © 2011 Elsevier B.V.
Type
research article
Scopus ID
2-s2.0-82955220456
Author(s)
Bentz, Cédric
Laboratoire Interdisciplinaire des Sciences du Numérique
Costa, Marie Christine
ENSTA Paris
École Polytechnique Fédérale de Lausanne
Picouleau, Christophe
Conservatoire National des Arts et Metiers
Ries, Bernard
Université Paris-Dauphine
Date Issued
2011-12-01
Publisher
Published in
Volume
38
Start page
129
End page
134
Subjects
Editorial or Peer reviewed
REVIEWED
Written at
EPFL
EPFL units
Available on Infoscience
February 4, 2026
Use this identifier to reference this record