A branch and bound algorithm for the matrix bandwidth minimization |
| |
Authors: | Rafael Martí ,Vicente CamposEstefaní a Piñ ana |
| |
Affiliation: | Departamento de Estadística e Investigación Operativa, Facultad de Matemáticas, Universitat de València, Dr. Moliner 50, 46100 Burjassot, València, Spain |
| |
Abstract: | In this article, we first review previous exact approaches as well as theoretical contributions for the problem of reducing the bandwidth of a matrix. This problem consists of finding a permutation of the rows and columns of a given matrix which keeps the non-zero elements in a band that is as close as possible to the main diagonal. This NP-complete problem can also be formulated as a labeling of vertices on a graph, where edges are the non-zero elements of the corresponding symmetrical matrix. We propose a new branch and bound algorithm and new expressions for known lower bounds for this problem. Empirical results with a collection of previously reported instances indicate that the proposed algorithm compares favourably to previous methods. |
| |
Keywords: | Branch and bound Optimization in graphs |
本文献已被 ScienceDirect 等数据库收录! |
|