Blockers and Transversals - ENSTA Paris - École nationale supérieure de techniques avancées Paris Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics Année : 2009

Blockers and Transversals

Rico Zenklusen
  • Fonction : Auteur
Bernard Ries
  • Fonction : Auteur
Christophe Picouleau
Marie-Christine Costa
Cédric Bentz

Résumé

We explore connections between d-blockers B in a graph G = (V;E) (i.e. subsets of edges whose removal decreases by at least d the cardinality of maximum matchings) and d-transversals T (i.e. subsets of edges such that every maximum matching M has at least d edges in T. Special classes of graphs are examined which include complete graphs, regular bipartite graphs, grid graphs, chains and cycles. We also study the complexity status of finding minimum transversals and blockers. Algorithms for d-transversals and d- blockers based on dynamic programming are given for trees.

Dates et versions

hal-00975349 , version 1 (08-04-2014)

Identifiants

Citer

Rico Zenklusen, Bernard Ries, Christophe Picouleau, Dominique de Werra, Marie-Christine Costa, et al.. Blockers and Transversals. Discrete Mathematics, 2009, 13, pp.4306--4314. ⟨10.1016/j.disc.2009.01.006⟩. ⟨hal-00975349⟩

Collections

ENSTA UMA_ENSTA
62 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More