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.
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

Identifiers

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⟩

Share

Metrics

Record views

214