【摘要】 本文提出了一个新的通孔最少化层分配的图模型．该模型克服了传统层分配算法对通孔度数和位置的限制，允许通孔自由地以任意度数和任何需要的位置出现．模型中还提出了通孔秩的概念，它比较能更精确地反映通孔的本质．在此基础上，本文将通孔最少化问题转化为图的最大割问题，并提出了一种启发式算法去求解图的最大割．算法已用Ｃ语言在ＳＵＮ工作站上实现．实验结果表明，算法十分有效且稳定．更多还原

【Abstract】 Abstract A new graphic model of layer assignment for via minimization is proposed.The model has overcome strict limitations of traditional layer assignment methods in via degree and location, and allows that the via appears with freedom in any degrees and anywhere.The conception of via rank is proposed in this model.It can represent the essence of via more precisely than degree of via.Then the via minimization problem is formulated as a maximum cut of weighted graph and a heuristic algorithm is used to solve it. The algorithm is implemented in C language under UNIX operating system on SUN workstation.Experiment results show that the algorithm is efficient and stable.更多还原