کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
477684 | 1446178 | 2008 | 16 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: A branch and bound algorithm for the matrix bandwidth minimization A branch and bound algorithm for the matrix bandwidth minimization](/preview/png/477684.png)
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.
Journal: European Journal of Operational Research - Volume 186, Issue 2, 16 April 2008, Pages 513–528