A hybrid evolutionary algorithm for the cutwidth minimization problem

Cutwidth minimization problem (CMP) consists of finding a linear layout of a graph such that the maximal number of cuts of a line separating consecutive vertices is minimized. CMP has significant applications in VLSI design, network communications, automatic graph drawings and information retrieval but it is proven to be a NP hard problem. Exact results of cutwidth are known for some classes of graphs but no algorithm has been proposed for the general graphs. In this paper, we present a hybrid evolutionary algorithm (HEA) for CMP which uses the depth first search of graph to generate the initial population and incorporates the simulated annealing in the selection process. HEA achieves the known optimal cutwidth of all the standard graphs tested. We also conjecture the cutwidth of some circulant graphs and generalized Peterson graphs supported by our experimental results.