首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号