Minimizing Profile of Graphs Using a Hybrid Simulating Annealing Algorithm

The profile minimization problem is a graph layout problem that consists of finding a linear arrangement (labeling) of vertices of a graph such that the sum of profiles of all vertices is minimum. The profile of a vertex can be defined as the difference of the position of its left most neighbor and the position of that vertex in the linear arrangement. It is an NP-complete problem with applications in the areas where the reordering of rows and columns of a sparse matrix is required in order to reduce the storage space. In this work, we propose a hybrid simulated annealing algorithm with the aim of profile reduction of a given graph by incorporating spectral sequencing for generating the initial solution. Experiments conducted on some benchmark graphs show that our algorithm outperforms the best existing algorithm in some cases and is comparable for rest of the instances. It also attains the optimal values for some classes of graphs with known optimal results.