ISSN:
1572-9338
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Notes:
Abstract 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02099694
Permalink