基于分支限界的关键路径求解算法

• 作者: 夏银水 王伦耀 胡美群
• 来源期刊: 宁波大学学报（理工版）
• 学科: 工学
• 关键词: 关键路径 分支限界 算法 时延 集成电路
• 年，卷（期）: 2011,（2）
• 所属期刊栏目: 通信工程与计算机应用
• 页码范围: 37-41
• 分类号: TP302
• 字数: 4980字
• 语种: 中文
• DOI: 10.3969/j.issn.1001-5132.2011.02.007

摘要

提出一种基于分支限界的关键路径求解算法,将电路拓扑结构表示成有向带权网(WOEN),寻找汇点,使节点到汇点的最大路径时延为该节点分支限界的最小限值,剪去违反分支限界最小限值的局部非关键路径的连接边以化简WOEN.新算法采取节点最大时延链表的存储结构,使得WOEN的存储空间、关键路径计算空间以及计算结果的存储空间共享同一存储空间.算法用C语言实现,并在ISCAS标准电路上加以测试.结果表明:新算法比现有算法所需的存储空间更小,求解关键路径的速度更快.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	夏银水	宁波大学信息科学与工程学院	101	345	9.0	13.0
2	王伦耀	宁波大学信息科学与工程学院	43	177	7.0	10.0
3	胡美群	宁波大学信息科学与工程学院	1	6	1.0	1.0