Abstract
Study of algorithms and its design can be progressed in various dimensions. In this paper, we have a definite refinement of lower bound on the number of tracks required to route a channel. The attack is from a complementary viewpoint. Our algorithm succeeds to avoid all kind of approximation. The approach performs exact mapping of the problem into graphical presentation and analyzes the graph taking help of mimetic algorithm, which uses combination of sequential and GA based vertex coloring. Performance of the algorithm depends on how effectively mimetic approach can applied selecting appropriate values for the parameters to evaluate the graphical presentation of the problem. This viewpoint has immense contribution against sticking at local minima for this optimization problem. The finer result clearly exemplifies instances, which give better or at least the same lower bound in VLSI channel routing problem.
Chapter PDF
Similar content being viewed by others
Key words
References
A.S. LaPaugh, Algorithm for integrated circuit layout: An analytic approach, Ph.D.dissertation, MIT Laboratory for Computer Science, Nov. 1980.
R.K Pal, S.P. Pal, A. Pal, On the Computational complexity of multiplayer channel routing, Technical Report: TR/IIT/CSE/92/02, Department of Computer Science and Engineering, Indian Institute of Technology, Kharagpur 721 302, India, 1992
R.K Pal, S.P. Pal, A.K. Datta, A. Pal, NP-completeness of multi-layer no-dogleg channel routing and an efficient heuristic, Proc. 6th Int. Conf. On VLSI Design, 1993, pp.80–83.
G.A. Scaper, Multi-layer channel routing, Ph.D. dissertation, Computer Science Department, University of Central Florida, Orlando, Fla., Aug. 1989.
M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980
Ricardo Blanco-vega, Jose Hernandez Orallo, Analyzing the Trade-off between comprehensibility & accuracy in Mimetic Models, Dept of System Informatics & Computation
Integration, the VLSI journal 25(1998) pp. 71–84.
Optimization for Engineering Design, Kalyanmoy Deb.
Pinaki Mazumder, Elizabeth M. Rudnick, Genetic Algorithms for VLSI Design, Layout & Test automation.
R.K. Pal, Multi-layer Channel Routing. Narosa Publishing House, India.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 International Federation for Information Processing
About this paper
Cite this paper
Saha, D., Pal, R.K., Sarma, S.S. (2006). A Mimetic Algorithm for Refinement of Lower Bound of Number of Tracks in Channel Routing Problem. In: Shi, Z., Shimohara, K., Feng, D. (eds) Intelligent Information Processing III. IIP 2006. IFIP International Federation for Information Processing, vol 228. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-44641-7_32
Download citation
DOI: https://doi.org/10.1007/978-0-387-44641-7_32
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-44639-4
Online ISBN: 978-0-387-44641-7
eBook Packages: Computer ScienceComputer Science (R0)