|
|||||
|
|
Blockers and transversals in some subclasses of bipartite graphs: When caterpillars are dancing on a grid |
|
| Authors: | B Ries |
| Institution: | a ETHZ, Eidgenössische Technische Hochschule Zürich, Zürich, Switzerland b Columbia University, New York, USA c CNAM, Laboratoire CEDRIC, Paris, France d EPFL, Ecole Polytechnique Fédérale de Lausanne, Lausanne, Switzerland e Université Paris-Sud, LRI, Orsay, France f ENSTA, UMA-CEDRIC, Paris, France |
| Abstract: | Given an undirected graph G=(V,E) with matching number ν(G), a d-blocker is a subset of edges B such that ν((V,E?B))≤ν(G)−d and a d-transversal T is a subset of edges such that every maximum matching M has |M∩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. |
| Keywords: | Transversal Blocker Matching Grid graph Tree Caterpillar |
| 本文献已被 ScienceDirect 等数据库收录！ | |