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

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

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

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(ns) and 0(n2), respectively. For the same storage requirements, the M-algorithm is superior to Kruskal's algorithm in computing.