A Min-Max Theorem for a Constrained Matching Problem
A Min-Max Theorem for a Constrained Matching Problem
复制标题
约束匹配问题的最小-最大定理
DOI：
10.1137/s0895480195280538
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
A. Hefner
中科院分区：
文献类型：
--
作者：
A. Hefner
下面的约束匹配问题出现在人力调度领域。考虑一个无向图$G=（V，E）$和一个有向图$D=（V，A）$。$G$中关于$D$的主/从匹配（MS匹配）是$G$中的匹配，使得对于A$中的每个弧$（u，v）\，节点$u$匹配，节点$v$也匹配。问题是找到最大基数的MS匹配。本文讨论了特殊的情况下，$G$是二部的二分区$V=W\cup U$和每个（弱）连接组件的$D$是一个孤立的节点或两个节点在$U$这是由一个单一的弧。研究了这种特殊情况下的多面体结构，并导出了一个极小极大定理，该定理用特殊节点覆盖的权来表征最大MS-匹配的基数。这个最小-最大定理包括柯尼希定理作为特例。
The following constrained matching problem arises in the area of manpower scheduling. Consider an undirected graph $G=(V,E)$ and a digraph $D=(V,A)$. A master/slave-matching (MS-matching) in $G$ with respect to $D$ is a matching in $G$ such that for each arc $(u,v)\in A$ for which the node $u$ is matched, the node $v$ is matched too. The problem is to find an MS-matching of maximum cardinality. This paper addresses the special case where $G$ is bipartite with bipartition $V=W\cup U$ and every (weakly) connected component of $D$ is either an isolated node or two nodes in $U$ which are joined by a single arc. The polyhedral structure of this special case is investigated and a min-max theorem which characterizes the cardinality of a maximum MS-matching in terms of the weight of a special node cover is derived. This min-max theorem includes as a special case the theorem of Konig.