The Feasible Matching Problem |
| |
Authors: | Yuejian Peng Papa A Sissokho |
| |
Institution: | 1. Hunan University, Changsha, Hunan, 410082, China 2. Indiana State University, Terre Haute, 47802, USA 3. Mathematics Department, Illinois State University, Normal, IL, 61790-4520, USA
|
| |
Abstract: | Let G = (V, E) be a graph and ${R\subseteq E}$ . A matching M in G is called R-feasible if the subgraph induced by the M-saturated vertices does not have an edge of R. We show that the general problem of finding a maximum size R-feasible matching in G is NP-hard and identify several natural applications of this new concept. In particular, we use R-feasible matchings to give a necessary and sufficient condition for the existence of a systems of disjoint representatives in a family of hypergraphs. This provides another Hall-type theorem for hypergraphs. We also introduce the concept of R-feasible (vertex) cover and combine it with the concept of R-feasible matching to provide a new formulation and approach to Ryser’s conjecture. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|