论文部分内容阅读
本文提出了一个新的通孔最少化层分配的图模型．该模型克服了传统层分配算法对通孔度数和位置的限制，允许通孔自由地以任意度数和任何需要的位置出现．模型中还提出了通孔秩的概念，它比较能更精确地反映通孔的本质．在此基础上，本文将通孔最少化问题转化为图的最大割问题，并提出了一种启发式算法去求解图的最大割．算法已用Ｃ语言在ＳＵＮ工作站上实现．实验结果表明，算法十分有效且稳定．
This paper presents a new via hole minimization layer graph model. This model overcomes the limitations of traditional layer allocation algorithms on the degree and location of vias, allowing the vias to appear freely in arbitrary degrees and at any desired location. The model also proposed the concept of through-hole rank, which more accurately reflect the nature of the through-hole. On this basis, this paper transforms the minimization of through-hole into the maximum-cut problem of graph, and proposes a heuristic algorithm to solve the maximum-cut of graph. The algorithm has been implemented in C language on a SUN workstation. Experimental results show that the algorithm is very effective and stable.