| 带有延迟时间下界的k-(n1,1,…,1)-排序问题的拟多项式时间算法 |
| |
| 引用本文： | 殷志文,沈靓.带有延迟时间下界的k-(n1,1,…,1)-排序问题的拟多项式时间算法[J].复旦学报(自然科学版),2005,44(2):224-230. |
| |
| 作者姓名： | 殷志文 沈靓 |
| |
| 作者单位： | 复旦大学,管理科学系,上海,200433 |
| |
| 摘 要： | 研究Wikum提到的关于带有延迟时间下界的k-(n1，1，…，1)-链形结构排序问题的拟多项式时间算法，其中n1=2的情况己得到解决，这里主要以n1=3的情形为例作更加细致的分析，然后给出此原来的算法更加有效的拟多项式时间算法．
|
| 关 键 词： | 排序 广义先后约束关系 NP完全问题 拟多项式时间算法 |
| 文章编号： | 0427-7104(2005)02-0224-07 |
Pseudo-polynomial Algorithm for the k- ( n1, 1,……, 1 ) - Chains Problem with Lower Bound Delays |
| |
| YIN Zhi-wen,SHEN Liang.Pseudo-polynomial Algorithm for the k- ( n1, 1,……, 1 ) - Chains Problem with Lower Bound Delays[J].Journal of Fudan University(Natural Science),2005,44(2):224-230. |
| |
| Authors: | YIN Zhi-wen SHEN Liang |
| |
| Abstract: | Study the pseudo-polynomial algorithm for the k-(n_1,1,...,1)- chains problem with lower bound delays which was discussed by Wikum.The problem of n_1=2 has been solved.With the analysis of the problem of n_1=3,a more efficient algorithm will be given. |
| |
| Keywords: | scheduling generalized precedence constraints NP-compelete pseudo-polynomial algorithm |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
