2种限制性指派问题  

Two kinds of constrained assignment problem

作　　者：黄斌超[1] 王海燕[1] 关莉[1] 李建平[1] 

机构地区：[1]云南大学数学系,云南昆明650091

出　　处：《云南大学学报（自然科学版）》2010年第5期510-515,共6页Journal of Yunnan University(Natural Sciences Edition)

基　　金：国家自然科学基金资助项目(10861012);云南省中青年学术技术带头人后备人才培养基金资助项目(2007PY01-21);云南大学理工科基金资助项目(2008YB024)

摘　　要：提出了指派问题的2种推广模型:双限制性指派问题和缺省限制性指派问题,首先设计了双限制性指派问题2种多项式算法,随后设计出了缺省限制性指派问题的1种多项式算法,并且分别对以上算法的正确性和时间复杂性做出了相应的证明.Two general kinds of corstrained assignment problem are given,called as the double-constrained assignment problem and the absent-constrained assignment problem,respectively.First of all,two polynomial time algorithms are designed for the first problem,and one polynomial-time algorithm is provided for the second problem.Finally,the validity and the complexity are proved for these three algorithms.

关 键 词：指派问题 缺省指派问题 Bellman-Ford算法 半匹配 

分 类 号：O157.5[理学—数学]