期刊
DISCRETE MATHEMATICS
卷 310, 期 1, 页码 132-146出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/j.disc.2009.08.009
关键词
Transversal; Blocker; Matching; Grid graph; Tree; Caterpillar
类别
资金
- ETHZ
- Fonds national de la recherche (Luxembourg) [TR-PDR BFR08-17]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据