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

• 作 者: 谢国平 姚林声
• 机 构: 中国科学院上海冶金研究所,中国科学院上海冶金研究所
• 出 处: 应用科学学报
• 发表日期: 1990年1期
• 关键词: LSI布线 设计 最优生成树 M-算法

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