位置：成果数据库 > 期刊 > 期刊详情页
背包类问题的并行O(25n/6)时间-空间-处理机折衷（英文）
  • ISSN号：1000-9825
  • 期刊名称：《软件学报》
  • 时间：0
  • 分类：TP301.6[自动化与计算机技术—计算机系统结构;自动化与计算机技术—计算机科学与技术]
  • 作者机构：湖南大学计算机与通信学院, 华中科技大学计算机学院 湖南长沙410082, 湖南长沙410082, 湖北武汉430074
  • 相关基金：国家自然科学基金No.60603053;国家教育部重点基金No.105128~~
作者： 李肯立, 赵欢, 李仁发, 李庆华
关键词： NP完全问题, 并行算法, 时间-空间-处理机折衷, 背包问题
中文摘要：

将串行动态二表算法应用于并行三表算法的设计中,提出一种求解背包、精确的可满足性和集覆盖等背包类NP完全问题的并行三表六子表算法.基于EREW-PRAM模型,该算法可使用O(2n/8)的处理机在O(27n/16)的时间和O(213n/48)的空间求解n维背包类问题,其时间-空间-处理机折衷为O(25n/6).与现有文献的性能对比分析表明,该算法极大地提高了并行求解背包类问题的时间-空间-处理机折衷性能.由于该算法能够破解更高维数的背包类公钥和数字水印系统,其结论在密钥分析领域具有一定的理论和实际意义.

同期刊论文项目
一种可扩展的DNA计算机模型研究与探索
期刊论文 52 会议论文 7
同项目期刊论文
一种最大匹配问题DNA计算算法
Convergence performance comparison of quantum-inspired multi-objective evolutionary algorithms
求解非线性方程组的混合人口迁移算法
一种基于DNA计算的指定结点路由算法
精确覆盖问题的O(1.414~n)链数DNA计算机算法
图3-着色问题的O(2~n)链数DNA计算机算法
O(1.414n) volume molecular solutions for the partition problem by DNA-based supercomputing
O(1.414n) volume molecular solutions for the subset-sum problem on DNA-based supercomputing
基于分治的子集积问题DNA计算机算法
基于分治的背包问题DNA计算机算法
Fast parallel molecular algorithms for DNA-based computation: Solving the elliptic curve discrete lo
一种改进的最大团问题DNA计算机算法(英文)
O(2n) volume molecular solutions for the 3-colorable problem on DNA-based supercomputing
DNA计算机中堆栈数据结构的设计
DNA计算机中基于顺序存储方式的二叉树数据结构
O(1.414n) volume molecular solutions for the exact cover problem on DNA-based supercomputing
背包类问题的并行O(2~(5n/6))时间-空间-处理机折衷(英文)
DNA计算机中二叉树的链式存储结构
图形处理器在分层聚类算法中的通用计算研究
Pollard p-1因子分解的DNA计算机算法
K-means初始聚类中心优化算法研究
基于CUDA的AES并行算法优化
求解药代动力学参数的混合人口迁移算法
求解单一重现期暴雨强度公式的Lingo-BFGS算法
一种改进的最大团问题DNA计算机算法
异构系统中一种基于可用性的抢占式任务调度算法
求解机械优化的Pareto多目标中心粒子群算法
求解非线性方程组的混合粒子群算法
求解非线性方程组的BFGS差分进化算法
哈密尔顿回路问题的DNA表面计算模型
精确覆盖问题的O（1．414^n）链数DNA计算机算法
子集和问题的O（1．414^n）链数DNA计算机算法
DNA计算机中二叉树存储结构的研究
基于粗糙集理论的ORD关联规则挖掘算法
背包类问题的并行O（2^5n/6）时间-空间-处理机折衷
基于分层聚类的并行数据预处理算法
一种基因数据的聚类并行算法研究
减小无刷直流电机转矩脉动的PWM新方式
最小生成树聚类方法研究
图3-着色问题的O（2^n）链数DNA计算机算法
一个矿山开采卫星监测系统的设计与实现
一种新的多波段遥感影像变化检测方法
期刊信息
  • 《软件学报》
  • 北大核心期刊（2011版）
  • 主管单位:中国科学院
  • 主办单位:中国科学院软件研究所 中国计算机学会
  • 主编：赵琛
  • 地址：北京8718信箱中国科学院软件研究所
  • 邮编：100190
  • 邮箱：jos@iscas.ac.cn
  • 电话：010-62562563
  • 国际标准刊号：ISSN：1000-9825
  • 国内统一刊号：ISSN：11-2560/TP
  • 邮发代号:82-367
  • 获奖情况:
  • 2001年入选中国期刊方阵“双百期刊”,2000年荣获中国科学院优秀科技期刊一等奖
  • 国内外数据库收录:
  • 俄罗斯文摘杂志,美国数学评论（网络版）,波兰哥白尼索引,德国数学文摘,荷兰文摘与引文数据库,美国工程索引,美国剑桥科学文摘,英国科学文摘数据库,日本日本科学技术振兴机构数据库,中国中国科技核心期刊,中国北大核心期刊（2004版）,中国北大核心期刊（2008版）,中国北大核心期刊（2011版）,中国北大核心期刊（2014版）,中国北大核心期刊（2000版）
  • 被引量:54609