Finding exact solutions to the bandwidth minimization problem
type: Item
instance of: scholarly article
title: Finding exact solutions to the bandwidth minimization problem
zbMATH Open document ID: 0946.65030
published in: Computing
publication date: 2000-10-17T00:00:00Z
review text: 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.
reviewed by: Michael Sever
Mathematics Subject Classification ID: 65F50
Mathematics Subject Classification ID: 05C78
Mathematics Subject Classification ID: 65F30
zbMATH DE Number: 1333223
zbMATH Keywords: bandwidth minimization
zbMATH Keywords: sparse symmetric matrix
zbMATH Keywords: NP-complete
zbMATH Keywords: algorithms
zbMATH Keywords: optimal ordering
author: Gianna M. Del Corso
author: Giovanni Manzini
MaRDI profile type: Publication
full work available at URL: s006070050002
OpenAlex ID: W2014044260
DOI: 10.1007/S006070050002
description: scientific article; zbMATH DE number 1333223