Journal
DISCRETE MATHEMATICS
Volume 310, Issue 1, Pages 132-146Publisher
ELSEVIER SCIENCE BV
DOI: 10.1016/j.disc.2009.08.009
Keywords
Transversal; Blocker; Matching; Grid graph; Tree; Caterpillar
Categories
Funding
- ETHZ
- Fonds national de la recherche (Luxembourg) [TR-PDR BFR08-17]
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available