摘要
在两区域电路线交叉分布中计算交叉点的数目,目前采用线性表或者动态规划的方法,其算法时间复杂性均为O(n2).为有效降低现有算法的时间复杂性,给出一种时间复杂性为O(nlogn)、利用树状数组的计数算法,并且可以找到每条布线的所有交叉线.理论分析和相应实验结果证实了该算法的有效性.
Counting the crossing wires in the crossing distribution of circuit wires between two regions, the current algorithms using either linear list or dynamic programming to do so have the time complexi- ty O (n2 ). In order to reduce the time complexity of the existing algorithms efficiently, a counting al- gorithm with the time complexity of O (nlogn) using arborescence array is introduced in this paper. Furthermore, all crossing wires of every circuit wire are found with this algorithm. The effectiveness of the algorithm is illustrated through the theoretical analysis and by the corresponding experiment re- sults.
出处
《福州大学学报(自然科学版)》
CAS
CSCD
北大核心
2013年第6期1028-1034,共7页
Journal of Fuzhou University(Natural Science Edition)
基金
福建省自然科学基金资助项目(2009J05142)
福州大学人才基金资助项目(0220826788)
福州大学科技发展基金资助项目(2011-xq-24)
关键词
电路布线
交叉分布
交叉线
树状数组
circuit wiring
crossing distribution
crossing wire
arborescence array