Please use this identifier to cite or link to this item:
標題: Topological Via Minimization Revisited
作者: M.Sarrafzadeh
出版社: IEEE Computer Society Washington, DC, USA
摘要: The topological via minimization problem in a two-layer environment is considered. A set of n two-terminal nets in a bounded region is given. The authors attempt to find a homotopy to assign nets to distinct layers so that no two nets on the same layer cross each other and the number of vias is minimized. A recursive approach in which an optimal solution to a two-sided channel routing problem is used as a basis is used to solve this problem optimally. The notion of partition number K of a circle graph is introduced, and the total running time of the via minimization algorithm is shown to be O((n/K)2K-2 log (n/K)), where n is the total number of nets
ISSN: 0018-9340
Appears in Collections:資訊科學與工程學系所



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.