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

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 vertical bar M boolean AND T vertical bar >= 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. (C) 2009 Elsevier B.V. All rights reserved.


Published in:
Discrete Mathematics, 310, 132-146
Year:
2010
Keywords:
Laboratories:




 Record created 2011-12-16, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)