A Genetic Algorithm Scheme to Solve Complex Triangle Problem

This book provides a scheme based on genetic algorithm (GA) to solve the complex triangle elimination (CTE) problem of rectangular dualization approach in VLSI floor planning. Rectangular dualization, where each module is realized as a rectangular area, is an important approach in VLSI floor planning. It is known that if the input adjacency graph contains a complex triangle (CT), i.e. a cycle of three edges that is not a face, and then its rectangular dual does not exists. Elimination of CTs therefore becomes essential before constructing a floor plan. There are two versions of the CTE problems -weighted and unweighted adjacency graphs. The weighted CTE problem is known to be NP-complete (Sun, 1993). Recently it has been proved that unweighted problem is also NP-complete. In this paper we present a genetic algorithmic scheme to solve unweighted CTE problem and weighted CTE problem.

Swapan Kumar Samaddar is a Senior Associate in Genpact India, Kolkata. He did BTech (CSE) from Netaji Subhash Engineering College, Kolkata and later on did his ME (CSE) from West Bengal University of Technology, Kolkata. His research areas are Digital Signal Processing, Image Processing, Advanced computer architecture and parallel architecture.