Abstract.
Given an \(m\times m\) sparse symmetric matrix, we consider the problem of finding the permutation of rows and columns which minimizes the bandwidth. This problem is known to be NP-complete therefore no algorithm polynomial in m is likely to exist. We present two algorithms which exhaustively enumerate all permutations trying to discard as early as possible those which cannot lead to an optimal ordering. Our first algorithm uses a depth first search strategy, while our second algorithm uses a recently developed technique called perimeter search. We have tested the performance of these algorithms solving problems of size ranging from 40 to 100. Our results show that there exist classes of matrices for which it is possible to find the minimum bandwidth in a small amount of time. Our results also provide additional experimental evidence of the effectiveness of the perimeter search technique: we found that, compared to depth-first search, perimeter search can reduce the running time up to a factor 100.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Author information
Authors and Affiliations
Additional information
Received: July 22, 1998; revised March 15, 1999
Rights and permissions
About this article
Cite this article
Del Corso, G., Manzini, G. Finding Exact Solutions to the Bandwidth Minimization Problem. Computing 62, 189–203 (1999). https://doi.org/10.1007/s006070050002
Issue Date:
DOI: https://doi.org/10.1007/s006070050002