Genetic algorithm for embedding a complete graph in a hypercube with a VLSI application

Abstract

The embedding of a complete graph in a minimum sized hypercube is an important problem which models the classical state encoding problem of Finite State Machines (FSMs). As this problem is an NP-hard optimization problem, acceptable final solutions are generally obtained by employing heuristic methods or Simulated Annealing (SA). In this paper the efficacy of a Genetic Algorithm (GA) for this problem is studied. This study includes a comparison of three different crossover methods of GA along with their implementation details and their suitability for this embedding problem. The experimental results on a number of MCNC benchmark FSMs indicate the superiority of GA in finding a better (near optimal) solution than a heuristic solution. These results experimentally establish the time efficiency of GA over SA for this embedding problem.