Finding exact solutions to the bandwidth minimization problem (Q1300222)

From MaRDI portal
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
    0 references
    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
    0 references
    0 references
    0 references
    0 references
    0 references
    bandwidth minimization
    0 references
    sparse symmetric matrix
    0 references
    NP-complete
    0 references
    algorithms
    0 references
    optimal ordering
    0 references
    0 references
    0 references
    0 references