Blockers and transversals in some subclasses of bipartite graphs

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

doi:10.1016/j.disc.2009.08.009

Back

Journal article

Blockers and transversals in some subclasses of bipartite graphs : When caterpillars are dancing on a grid

Ries, Bernard Columbia University, United States
Bentz, Cédric Université Paris-Sud
Picouleau, Christophe CNAM, France
de Werra, Dominique EPFL, Switzerland
Costa, Marie-Christine ENSTA, France
Zenklusen, Rico ETHZ, Switzerland

2010

Published in:

Discrete Mathematics. - 2010, vol. 310, p. 132-146

Theoretical Computer Science

Discrete Mathematics and Combinatorics

English Given an undirected graph G=(V,E) with matching number \nu(G), a d-blocker is a subset of edges B such that \nu(/V,E\B))<=\nu(G)-d and a d-transversal T is a subset of edges such that every maximum matching M has |M \cap T|>= d. While the associated decision 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.

Faculty

Faculté des sciences économiques et sociales et du management

Department

Département d'informatique

Language