English

应用科学学报 ›› 1990, Vol. 8 ›› Issue (1): 41-46.

• 论文 • 上一篇    下一篇

LSI布线设计中的最优树算法研究

谢国平, 姚林声   

  1. 中国科学院上海冶金研究所
  • 收稿日期:1987-02-25 修回日期:1987-09-18 出版日期:1990-03-31 发布日期:1990-03-31

THE INVESTIGATION OF ALGORITHM FOR THE SMALLEST WEIGHT SPANNING TREE IN LSI ROUTING

XIE GUOPING, YAO LINSHENG   

  1. Shanghai Institute of Metallurgy, Academia Sinica
  • Received:1987-02-25 Revised:1987-09-18 Online:1990-03-31 Published:1990-03-31

PDF

65

摘要： 本文讨论了在集成电路的布线设计中所碰到的求无向完全图的最优生成树问题,提出了一种求最优树的上三角阵算法(简称M-算法).描述了支持这种算法的数据结构.对完全图G(n,e),M-算法的计算复杂性是O (n3),空间复杂性是O (n2),在相同的空间复杂性条件下,比直接用Kruskal算法要优越.

Abstract: In this paper, the smallest weight spanning tree in the non-oriented complete graph, which is usually encountered in IC's routing, is discussed. An algorithm for finding the smallest weight spanning tree is presented. It is called the upper-triangular-matrix algorithm (briefly as M-algorithm). The data structure that supports the algorithm is described. For the complete graph G(n, e), the complexities in computing and in storage of the M-algorithm are 0(n3) and 0(n2), respectively. For the same storage requirements, the M-algorithm is superior to Kruskal's algorithm in computing.