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. Blockers and transversals
 
research article

Blockers and transversals

Zenklusen, Rico
•
Ries, Bernard
•
Picouleau, Christophe
Show more
2009
Discrete Mathematics

Given an undirected graph G = (V, E) with matching number v(G), we define d-blockers as subsets of edges B such that nu((V, E \ B)) <= nu(G) - d. We define d-transversals T as subsets of edges such that every maximum matching M has |M boolean AND T| >= d. We explore connections between d-blockers and d-transversals. Special classes of graphs are examined which include complete graphs, regular bipartite graphs, chains and cycles and we construct minimum d-transversals and d-blockers in these special graphs. We also study the complexity status of finding minimum transversals and blockers in arbitrary graphs. (C) 2009 Elsevier B.V. All rights reserved.

  • Details
  • Metrics
Type
research article
DOI
10.1016/j.disc.2009.01.006
Web of Science ID

WOS:000266760400013

Author(s)
Zenklusen, Rico
Ries, Bernard
Picouleau, Christophe
de Werra, Dominique
Costa, Marie-Christine
Bentz, Cédric
Date Issued

2009

Publisher

Elsevier

Published in
Discrete Mathematics
Volume

309

Issue

13

Start page

4306

End page

4314

Subjects

Transversal

•

Blocker

•

Matching

•

Complete graph

•

Complete bipartite graph

•

Deletion Problems

•

Bipartite Graphs

•

Matchings

•

Complexity

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
TRANSP-OR  
Available on Infoscience
September 30, 2010
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/54456
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