Blockers and Transversals

Abstract : 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.
Type de document :
Article dans une revue
Discrete Mathematics, Elsevier, 2009, 13, pp.4306--4314. 〈10.1016/j.disc.2009.01.006〉
Liste complète des métadonnées

https://hal-ensta.archives-ouvertes.fr/hal-00975349
Contributeur : Aurélien Arnoux <>
Soumis le : mardi 8 avril 2014 - 14:36:00
Dernière modification le : mercredi 6 décembre 2017 - 16:46:01

Lien texte intégral

Identifiants

Collections

Citation

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

Partager

Métriques

Consultations de la notice

77