6533b871fe1ef96bd12d237e

RESEARCH PRODUCT

A branch and bound algorithm for the matrix bandwidth minimization

Vicente CamposEstefanía PiñanaRafael Martí

subject

Information Systems and ManagementDegree matrixBand matrixGeneral Computer ScienceBranch and boundBlock matrixManagement Science and Operations ResearchPermutation matrixIndustrial and Manufacturing EngineeringCombinatoricsModeling and SimulationCuthill–McKee algorithmDiagonal matrixMathematicsSparse matrix

description

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.

yearjournalcountryeditionlanguage
2008-04-01European Journal of Operational Research
https://doi.org/10.1016/j.ejor.2007.02.004