Back to Search
Start Over
A MIN-MAX THEOREM FOR A CONSTRAINED MATCHING PROBLEM.
- Source :
-
SIAM Journal on Discrete Mathematics . 1997, Vol. 10 Issue 2, p180-189. 10p. - Publication Year :
- 1997
-
Abstract
- 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) ∈ 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 ∪ 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 König. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 10
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 13219506
- Full Text :
- https://doi.org/10.1137/S0895480195280538