An unfeasible matching problem |
| |
Authors: | Andrzej Lingas |
| |
Affiliation: | (1) Department of Computer Science, Lund University, Box 118, 22100 Lund, Sweden |
| |
Abstract: | LetG be a bipartite graph with natural edge weights, and letW be a function from the set of vertices ofG into natural numbers. AW-matching ofG is a subset of the set of edges ofG such that for each vertexv the total weight of edges in the subset incident tov does not exceedW(v). Letm be a natural number. We show that the problem of deciding whether there is aW-matching inG whose total weight is not less thanm is NP-complete even ifG is bipartite and its edge weights as well as theW(v)-constraints are constantly bounded. |
| |
Keywords: | F.1.3 G.2.2 |
本文献已被 SpringerLink 等数据库收录! |
|