Graph Partitioning Technique for Separating Nets in ,Single-row Networks
Single-row routing is fundamentally a routing technique for pairs of nodes arranged in a single-row axis.It contributes in the printed circuit board (PCB) design.The main objective in single-row routing is to achieve minimum congestion arising from the number of horizontal tracks in the network.Optimal results for a single layer network have been achieved through our previous model called ESSR.However,a single layer model suffers from non-tolerable lower bound values wth high congestion depending on the network size.These results may further be improved by partitioning the network into two or more layers.In this paper,we propose a technique based on the graph partitioning concept for partitioning the nodes from a single-row network into several layers of planar graphs.The experiment result shows that the proposed technique is able to decrease the network congestions.
Single-row routing ESSR graph partitioning maximum clique Kernighan-Lin algorithm
Norazaliza Mohd.Jamil Noraziah Ahmad Shaharuddin Salleh
Faculty of Computer Systems & Software Engineering,Universiti Malaysia Pahang,Locked Bag 12,25000,Ku Department of Mathematics,Faculty of Science,Universiti Teknologi Malaysia,81310,Johor Bahru,Malaysi
国际会议
大连
英文
775-779
2008-07-27（万方平台首次上网日期，不代表论文的发表时间）