R. Chandrasekharam et al., GENETIC ALGORITHM FOR NODE PARTITIONING PROBLEM AND APPLICATIONS IN VLSI DESIGN, IEE proceedings. Part E. Computers and digital techniques, 140(5), 1993, pp. 255-260
The group of classical graph-theoretic problems, including graph colou
ring, clique cover, and maximal clique, may be viewed as instances of
a general node partitioning problem (NPP). A wide variety of real life
problems can be modelled as instances of NPP. Finding an optimal part
ition for the NPP is said to be NP-complete. In this work a stochastic
search by a genetic algorithm (GA) is employed to find a near optimal
solution for the NPP. The critical aspects of the GA for NPP, such as
the solution representation by elegant data structure, together with
genetic operations and selection policies employed in the GA procedure
, are also presented. The proposed GA does not require the number of d
isjunct node sets to be given a priori. Three application problems is
VLSI design are solved as instances of NPP. The experimental results p
resented in each case of these application problems bring out the effi
cacy of genetic algorithms.