关于印刷电路及大规模集成电路布线设计的理论研究

在集成电路和印刷电路的版图设计中,电路的布线是一个具有重大实际意义的问题。葛守仁教授应用图论、优化理论等数学工具,对集成电路的布线进行了理论研究,并已经取得了可喜的成果。本文介绍了一种寻求最佳互连(interconnection)方案的方法。著者通过和布线图对应的区间图(interval graph)找出一种“通路稠密度”(street congestion)最小的方案,以达到用最小的版面获得最大的布线数的目的。著者进一步论证了对应于各种布局(Piacement)的区间图中,“包采数”(chromatical number)最小的就代表最佳的布局。