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

Bernard Ries; Cédric Bentz; Dominique de Werra; Marie-Christine Costa; Rico Zenklusen; Christophe Picouleau

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

Bernard Ries ¹ Cédric Bentz ² Dominique de Werra ^{1, 3} Marie-Christine Costa ^{3, 2} Rico Zenklusen ¹ Christophe Picouleau ²

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

Domain :

Computer Science [cs] / Operations Research [cs.RO]

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

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

Links full text

Identifiers

Collections

Citation

Export

Metrics

205

Contact

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

Links full text

Identifiers

Collections

Citation

Export

Share

Metrics

205

Contact