单台机器多链时间约束问题的若干新结果

摘要

在本文中，我们针对Ｗｉｋｕｍ等人在文（４）中提出的单台机器多链时间约束问题的若干个公开问题给出了一些新的结果。我们证明了带有延迟时间上界的ｋ－２－链形结构的排序问题是ＮＰ－困难的，并分别对带有延迟时间上界／下界的ｋ－（２，１，．．．，１）－链形结构问题给出了一个拟多项式时间算法。