| 引用本文: | 晓斌,张干宗.瓶颈指派问题的一种多项式时间算法.[J].国防科技大学学报,1997,19(1):94-98.[点击复制] |
| Xiao Bin,Zhang Ganzong.A Polynomial-time Algorithm for the Bottleneck Assignment Problem[J].Journal of National University of Defense Technology,1997,19(1):94-98[点击复制] |
|
| |
|
|
| 本文已被：浏览 6648次 下载 6851次 |
| 瓶颈指派问题的一种多项式时间算法 |
| 晓斌, 张干宗 |
|
(国防科技大学 系统工程与数学系 湖南 长沙 410073)
|
| 摘要: |
| 本文对瓶颈指派问题给出了一种新的算法, 该算法不需要利用最大流算法, 而类似于解经典指派问题的匈牙利算法。该算法是一个多项式时间算法, 其复杂性为O(n3). |
| 关键词: 瓶颈指派问题, 多项式时间算法, 阀门算法。 |
| DOI： |
| 投稿日期：1995-11-14 |
| 基金项目: |
|
| A Polynomial-time Algorithm for the Bottleneck Assignment Problem |
| Xiao Bin, Zhang Ganzong |
|
(Department of Systems Engineering and Mathematics, NUDT, Changsha, 410073)
|
| Abstract: |
| In this paper, we give a new algorithm for the bottleneck assignment problem on the basis of Konig's theorem, and show that the time complexity of the algorithm is O(n3). |
| Keywords: bottleneck assignment problem polynomial-time algorithm threshold algorithm |
|
|
|
|
|
