Finding Exact Solutions to the Bandwidth Minimization Problem
Copyright policy )Finding Exact Solutions to the Bandwidth Minimization Problem
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.
- University of Pisa Italy
- National Research Council Italy
- Università del Piemonte Orientale Italy
Graph labelling (graceful graphs, bandwidth, etc.), Computational methods for sparse matrices, sparse symmetric matrix, Other matrix algorithms, bandwidth minimization, algorithms, optimal ordering, NP-complete
Graph labelling (graceful graphs, bandwidth, etc.), Computational methods for sparse matrices, sparse symmetric matrix, Other matrix algorithms, bandwidth minimization, algorithms, optimal ordering, NP-complete
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).30 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!