G-Tree:基于引力指向技术减少拐弯的Steiner树算法

摘要：

提出一种基于引力指向技术、以减少拐弯数为目标的最小直角Steiner树构造算法G-Tree.利用一个节点受到其他节点的引力来决定它的移动方向,并采用引力加权以考虑减少拐弯数,生成Steiner树后对拐弯数进行了进一步优化.减少拐弯数有助于在布线阶段减少可能的通孔,从而增强电路的可靠性和可制造性.实验结果表明,G-Tree算法在减少布线树的拐弯数方面有明显的效果.

关键词：Steiner树、拐弯、通孔

所属期刊栏目：20

分类号：TP391(计算技术、计算机技术)

资助基金：国家自然科学基金90407005;90607001;教育部科学技术研究项目106008;高等学校博士学科点专项科研项目20050003099

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

页数：共5页

页码：144-148