Finding exact solutions to the bandwidth minimization problem

DOI10.1007/S006070050002MaRDI QIDQ1300222zbMATH OpenOpenAlexFDO

Authors Gianna M. Del Corso, Giovanni Manzini

Publication date 17 October 2000

Published in Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s006070050002

zbMATH Keywords

algorithmsbandwidth minimizationNP-completeoptimal orderingsparse symmetric matrix

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational methods for sparse matrices (65F50)

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.

Recommendations

• A branch and bound algorithm for the matrix bandwidth minimization
• A general strategy on the bandwidth minimization (BM) problem
• A new matrix bandwidth reduction algorithm
• On the Probable Performance of Heuristics for Bandwidth Minimization
• A constructive bandwidth reduction algorithm

Cited in

(16)

• On bandwidth-2 graphs
• GRASP and path relinking for the matrix bandwidth minimization.
• Variable neighbourhood search for bandwidth reduction
• A branch and bound algorithm for the matrix bandwidth minimization
• An improved simulated annealing algorithm for bandwidth minimization
• Reducing the bandwidth of a sparse matrix with a genetic algorithm
• Exact and heuristic solutions to the bandwidth minimization problem
• A general strategy on the bandwidth minimization (BM) problem
• The Effective Bandwidth Problem Revisited
• On the Probable Performance of Heuristics for Bandwidth Minimization
• scientific article; zbMATH DE number 1748479 (Why is no real title available?)
• A dual representation simulated annealing algorithm for the bandwidth minimization problem on graphs
• Parallel computation for the bandwidth minimization problem
• A survey of direct methods for sparse linear systems
• Efficient iterated greedy for the two-dimensional bandwidth minimization problem
• Exact and approximate bandwidth

This page was built for publication: Finding exact solutions to the bandwidth minimization problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1300222)