A learning automaton based approach to solve the graph bandwidth minimization problem

In this paper we develop a novel approximated procedure for the problem of reducing the bandwidth of a graph. This problem consists of finding a permutation of the rows and columns of a given matrix, which keeps the nonzero elements in a band that is as close as possible to the main diagonal. The new algorithm is based on object migration learning automaton. The algorithm is evaluated on a set of 113 well-known benchmark instances of the literatures and compared with several state-of-the-art algorithms, showing improvements of some previous best results. The positive point of the new proposed algorithm that it can balance the quality of results and running times. So the algorithm can lead to good results in a short running time.