Loading...
research article
Blockers and transversals in some subclasses of bipartite graphs: When caterpillars are dancing on a grid
2010
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.
Type
research article
Web of Science ID
WOS:000272437800016
Authors
Publication date
2010
Published in
Volume
310
Start page
132
End page
146
Peer reviewed
REVIEWED
EPFL units
Available on Infoscience
December 16, 2011
Use this identifier to reference this record