Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Minimum d-Transversals of Maximum-Weight Stable Sets in Trees
 
research article

Minimum d-Transversals of Maximum-Weight Stable Sets in Trees

Bentz, Cédric
•
Costa, Marie Christine
•
de Werra, Dominique  
Show more
December 1, 2011
Electronic Notes in Discrete Mathematics

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.

  • Details
  • Metrics
Type
research article
DOI
10.1016/j.endm.2011.09.022
Scopus ID

2-s2.0-82955220456

Author(s)
Bentz, Cédric

Laboratoire Interdisciplinaire des Sciences du Numérique

Costa, Marie Christine

ENSTA Paris

de Werra, Dominique  

É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

Elsevier

Published in
Electronic Notes in Discrete Mathematics
Volume

38

Start page

129

End page

134

Subjects

Maximum-weight stable sets

•

Transversals

•

Trees

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
ROSE  
Available on Infoscience
February 4, 2026
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/258893
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés