带有延迟时间下界的k-(n1,1,…,1)-排序问题的拟多项式时间算法

摘要：

讨论Wikum的关于带有延迟时间下界的k-(n1,1,…,1)-链形结构排序问题的拟多项式时间算法,其中当n1=2的情况已由Yin等人(1999)解决,这里主要以n1=3的情形为例作更加细致的分析,然后给出较Yin等人(1999)的算法更加有效的拟多项式时间算法.为了保持文章的连续性,也将列出Yin等人(1999)的n1=2的算法加以比较.

关键词：排序、广义先后约束关系、NP完全问题、拟多项式时间算法

所属期刊栏目：19

分类号：O223(运筹学)

在线出版日期：2005-09-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：593-600