Finding exact solutions to the bandwidth minimization problem (Q1300222): Difference between revisions
From MaRDI portal
Changed an Item |
Set OpenAlex properties. |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
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