引用本文: | 晓斌,张干宗.瓶颈指派问题的一种多项式时间算法[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[点击复制] |
|
|
|
本文已被:浏览 6190次 下载 6216次 |
瓶颈指派问题的一种多项式时间算法 |
晓斌, 张干宗 |
(国防科技大学 系统工程与数学系 湖南 长沙 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 |
|
|
|
|
|