| G-Tree:基于引力指向技术减少拐弯的Steiner树算法 |
| |
| 引用本文： | 梁敬弘,洪先龙,经彤.G-Tree:基于引力指向技术减少拐弯的Steiner树算法[J].计算机辅助设计与图形学学报,2008,20(2):144-148. |
| |
| 作者姓名： | 梁敬弘 洪先龙 经彤 |
| |
| 作者单位： | 清华大学计算机科学与技术系,北京,100084 |
| |
| 基金项目： | 国家自然科学基金
,
教育部科学技术研究项目
,
高等学校博士学科点专项科研项目 |
| |
| 摘 要： | 提出一种基于引力指向技术、以减少拐弯数为目标的最小直角Steiner树构造算法G-Tree.利用一个节点受到其他节点的引力来决定它的移动方向,并采用引力加权以考虑减少拐弯数,生成Steiner树后对拐弯数进行了进一步优化.减少拐弯数有助于在布线阶段减少可能的通孔,从而增强电路的可靠性和可制造性.实验结果表明,G-Tree算法在减少布线树的拐弯数方面有明显的效果.
|
| 关 键 词： | Steiner树 拐弯 通孔 |
| 收稿时间： | 2007-06-15 |
| 修稿时间： | 2007-10-24 |
G-Tree: Gravitation-Direction-Based Rectilinear Steiner Minimal Tree Construction Considering Bend Reduction |
| |
| Liang Jinghong,Hong Xianlong,Jing Tong.G-Tree: Gravitation-Direction-Based Rectilinear Steiner Minimal Tree Construction Considering Bend Reduction[J].Journal of Computer-Aided Design & Computer Graphics,2008,20(2):144-148. |
| |
| Authors: | Liang Jinghong Hong Xianlong Jing Tong |
| |
| Abstract: | This paper presents a RSMT algorithm based on gravitation direction, namely G-Tree. It uses the gravitation a point receives from other points to judge its moving direction. Some weights are added to the calculation to reduce the number of bends, which is helpful for via reduction and reliability increment in the routing phase. After the construction, some refinements are taken to reduce bends further more. G-Tree has been implemented and tested. The experimental results show that G-Tree can reduce numbers of bends. |
| |
| Keywords: | Steiner tree bend via |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
