带有延迟时间下界的k-(n1,1,…,1)-排序问题的拟多项式时间算法 |
| |
引用本文: | 殷志文,沈靓.带有延迟时间下界的k-(n1,1,…,1)-排序问题的拟多项式时间算法[J].复旦学报(自然科学版),2005,44(2):224-230. |
| |
作者姓名: | 殷志文 沈靓 |
| |
作者单位: | 复旦大学,管理科学系,上海,200433;复旦大学,管理科学系,上海,200433 |
| |
摘 要: | 研究Wikum提到的关于带有延迟时间下界的k-(n1,1,…,1)-链形结构排序问题的拟多项式时间算法,其中n1=2的情况己得到解决,这里主要以n1=3的情形为例作更加细致的分析,然后给出此原来的算法更加有效的拟多项式时间算法.
|
关 键 词: | 排序 广义先后约束关系 NP完全问题 拟多项式时间算法 |
文章编号: | 0427-7104(2005)02-0224-07 |
本文献已被 CNKI 维普 万方数据 等数据库收录! |
|