Blockers and Transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid

Abstract : Given an undirected graph G = (V;E) with matching number n(G), a d-blocker is a subset of edges B such that n((V;E-B))< ou = n(G)- d and a d-transversal T is a subset of edges such that every maximum matching M has at least d edges in T. While the problem is NP-complete in bipartite graphs we show how to construct efficiently minimum d-transversals and minimum d-blockers in the special cases where G is a grid graph or a tree.
Type de document :
Article dans une revue
Discrete Mathematics, Elsevier, 2010, 310, pp.132--146. 〈10.1016/j.disc.2009.08.009〉
Liste complète des métadonnées

https://hal-ensta.archives-ouvertes.fr/hal-00974959
Contributeur : Aurélien Arnoux <>
Soumis le : lundi 7 avril 2014 - 16:46:47
Dernière modification le : jeudi 13 septembre 2018 - 15:24:07

Lien texte intégral

Identifiants

Collections

Citation

Bernard Ries, Cédric Bentz, Dominique De Werra, Marie-Christine Costa, Rico Zenklusen, et al.. Blockers and Transversals in some subclasses of bipartite graphs: when caterpillars are dancing on a grid. Discrete Mathematics, Elsevier, 2010, 310, pp.132--146. 〈10.1016/j.disc.2009.08.009〉. 〈hal-00974959〉

Partager

Métriques

Consultations de la notice

135