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

Bernard Ries 1 Cédric Bentz 2 Dominique de Werra 1, 3 Marie-Christine Costa 3, 2 Rico Zenklusen 1 Christophe Picouleau 2
1 Département de Mathématiques - EPFL
2 CEDRIC - Centre d'études et de recherche en informatique et communications
3 OC - Optimisation et commande
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.
Document type :
Journal articles
Complete list of metadatas
https://hal-ensta-paris.archives-ouvertes.fr//hal-00974959
Contributor : Aurélien Arnoux <>
Submitted on : Monday, April 7, 2014 - 4:46:47 PM
Last modification on : Wednesday, July 3, 2019 - 10:48:04 AM

Links full text

openaccess

Identifiers

Collections

ENSTA | UMA_ENSTA | CNAM | UNIV-HESAM | CEDRIC-CNAM

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⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

214

Contact

Informations

CCSD