A Mimetic Algorithm for Computing a Nontrivial Lower Bound on Number of Tracks in Two-Layer Channel Routing

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 kinds 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 be 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.