Finding exact solutions to the bandwidth minimization problem (Q1300222): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/s006070050002 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2014044260 / rank | |||
Normal rank |
Latest revision as of 22:17, 19 March 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