提示
李肯立
-
37浏览
-
0点赞
-
0收藏
-
0分享
-
89下载
-
0评论
-
引用
期刊论文
背包类问题的并行O(25n/6)时间-空间-处理机折衷∗
JournalofSoftware，2007，18（6）：1319～1327，-0001，（）：
将串行动态二表算法应用于并行三表算法的设计中,提出一种求解背包、精确的可满足性和集覆盖等背包类NP完全问题的并行三表六子表算法。基于EREW-PRAM模型,该算法可使用O（2n/8）的处理机在O（27n/16）的时间和O（213n/48）的空间求解n维背包类问题,其时间-空间-处理机折衷为O（25n/6）。与现有文献的性能对比分析表明,该算法极大地提高了并行求解背包类问题的时间-空间-处理机折衷性能。由于该算法能够破解更高维数的背包类公钥和数字水印系统,其结论在密钥分析领域具有一定的理论和实际意义。
【免责声明】以下全部内容由[李肯立]上传于[2009年12月22日 16时28分29秒]，版权归原创者所有。本文仅代表作者本人观点，与本网站无关。本网站对文中陈述、观点判断保持中立，不对所包含内容的准确性、可靠性或完整性提供任何明示或暗示的保证。请读者仅作参考，并请自行承担全部责任。
本学者其他成果
同领域成果
