A constrained matching problem
A constrained matching problem
复制标题
约束匹配问题
DOI：
10.1007/bf02099694
复制
发表时间：
1995
影响因子：
4.8
通讯作者：
P. Kleinschmidt
中科院分区：
文献类型：
--
作者：
A. Hefner;P. Kleinschmidt
我们表明，某些人力调度问题可以建模为以下约束匹配问题。给定一个带边权的无向图G =（V，E）和一个有向图D =（V，A）。G相对于D的A主/从匹配（MS匹配）是G的匹配，使得对于节点u匹配的每个弧（u，v）εA，节点dev也匹配。MS匹配问题是寻找最大权MS匹配的问题。设k（D）是D的（弱）连通分支的最大尺寸。证明了即使G是二部的且k（D）≤ 3，MS匹配也是NP-难问题.此外，我们还证明了在k（D）≤ 2的特殊情况下，MS-匹配问题可以转化为普通的匹配问题.
We show that certain manpower scheduling problems can be modeled as the following constrained matching problem. Given an undirected graphG = (V,E) with edge weights and a digraphD = (V,A). AMaster/Slave-matching (MS-matching) ofG with respect toD is a matching ofG such that for each arc (u, v) εA for which the nodeu is matched, the nodev is matched, too. TheMS-Matching Problem is the problem of finding a maximum-weight MS-matching. Letk(D) be the maximum size of a (weakly) connected component ofD. We prove that MS-matching is an NP-hard problem even ifG is bipartite andk(D) ≤ 3. Moreover, we show that in the relevant special case wherek(D) ≤ 2, the MS-Matching Problem can be transformed to the ordinary Matching Problem.