| 2种限制性指派问题 |
| |
| 引用本文： | 黄斌超,王海燕,关莉,李建平. 2种限制性指派问题[J]. 云南大学学报(自然科学版), 2010, 32(5): 510-515 |
| |
| 作者姓名： | 黄斌超 王海燕 关莉 李建平 |
| |
| 作者单位： | 云南大学数学系; |
| |
| 基金项目： | 国家自然科学基金资助项目(10861012); 云南省中青年学术技术带头人后备人才培养基金资助项目(2007PY01-21); 云南大学理工科基金资助项目(2008YB024) |
| |
| 摘 要： | 提出了指派问题的2种推广模型:双限制性指派问题和缺省限制性指派问题,首先设计了双限制性指派问题2种多项式算法,随后设计出了缺省限制性指派问题的1种多项式算法,并且分别对以上算法的正确性和时间复杂性做出了相应的证明.
|
| 关 键 词： | 指派问题 缺省指派问题 Bellman-Ford 算法 半匹配 |
| 收稿时间： | 2010-01-15 |
Two kinds of constrained assignment problem |
| |
| HUANG Bin-chao,WANG Hai-yan,GUAN Li,LI Jian-ping. Two kinds of constrained assignment problem[J]. Journal of Yunnan University(Natural Sciences), 2010, 32(5): 510-515 |
| |
| Authors: | HUANG Bin-chao WANG Hai-yan GUAN Li LI Jian-ping |
| |
| Affiliation: | HUANG Bin-chao,WANG Hai-yan,GUAN Li,LI Jian-ping(Department of Mathematics,Yunnan University,Kunming 650091,China) |
| |
| Abstract: | 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. |
| |
| Keywords: | assignment problem absent assignment problem Bellman-Ford algorithm semi-matching |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《云南大学学报(自然科学版)》浏览原始摘要信息 |
|
点击此处可从《云南大学学报(自然科学版)》下载全文 |
