Finding exact solutions to the bandwidth minimization problem (Q1300222): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claims |
||
Property / author | |||
Property / author: Gianna M. Del Corso / rank | |||
Property / author | |||
Property / author: Giovanni Manzini / rank | |||
Revision as of 22:37, 10 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Finding exact solutions to the bandwidth minimization problem |
scientific article |
Statements
Finding exact solutions to the bandwidth minimization problem (English)
0 references
17 October 2000
0 references
Given an \(m\times m\) sparse symmetric matrix, the authors consider the problem of finding the permutation of rows and columns which minimizes the bandwidth. The problem is known to be NP-complete; therefore no polynomial algorithm in \(m\) is likely to exist. They present two algorithms which exhaustively enumerate all permutations, trying to discard as early as possible those which cannot lead to an optimal ordering.
0 references
bandwidth minimization
0 references
sparse symmetric matrix
0 references
NP-complete
0 references
algorithms
0 references
optimal ordering
0 references