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-blockers and d-transversals in graphs
 
research article

Minimum d-blockers and d-transversals in graphs

Costa, Marie-Christine
•
de Werra, Dominique  
•
Picouleau, Christophe
2011
Journal Of Combinatorial Optimization

We consider a set V of elements and an optimization problem on V: the search for a maximum (or minimum) cardinality subset of V verifying a given property a"similar to. A d-transversal is a subset of V which intersects any optimum solution in at least d elements while a d-blocker is a subset of V whose removal deteriorates the value of an optimum solution by at least d. We present some general characteristics of these problems, we review some situations which have been studied (matchings, s-t paths and s-t cuts in graphs) and we study d-transversals and d-blockers of stable sets or vertex covers in bipartite and in split graphs.

  • Details
  • Metrics
Type
research article
DOI
10.1007/s10878-010-9334-6
Web of Science ID

WOS:000296520200025

Author(s)
Costa, Marie-Christine
de Werra, Dominique  
Picouleau, Christophe
Date Issued

2011

Published in
Journal Of Combinatorial Optimization
Volume

22

Start page

857

End page

872

Subjects

Transversal

•

Blocker

•

Cover

•

Bipartite graph

•

Split graph

•

s-t path

•

s-t cut

•

Stable set

•

Bilevel programming

•

Deletion Problems

•

Number

•

Trees

•

Sets

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
ROSE  
Available on Infoscience
December 16, 2011
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/73348
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