ScholarLens Back to search
1978•SIAM Journal on Applied MathematicsRequires access

Complexity Results for Bandwidth Minimization

Michael R. Garey, Ronald Graham, David S. Johnson, D. E. Knuth

Open publisher page 295 citations

Abstract

We present a linear-time algorithm for sparse symmetric matrices which converts a matrix into pentadiagonal form (“bandwidth 2”), whenever it is possible to do so using simultaneous row and column permutations. On the other hand when an arbitrary integer k and graph G are given, we show that it is $NP$-complete to determine whether or not there exists an ordering of the vertices such that the adjacency matrix has bandwidth $ \leqq k$, even when G is restircted to the class of free trees with all vertices of degree $ \leqq 3$. Related problems for acyclic directed graphs (upper triangular matrices) are also discussed.

About this research paper

What this paper is about

We present a linear-time algorithm for sparse symmetric matrices which converts a matrix into pentadiagonal form (“bandwidth 2”), whenever it is possible to do so using simultaneous row and column permutations. On the other hand when an arbitrary integer k and graph G are given, we show that it is $NP$-complete to determine whether or not there exists an ordering of the vertices such that the adjacency matrix has bandwidth $ \leqq k$, even when G is restircted to the class of free trees with all vertices of degree $ \leqq 3$. Related problems for acyclic directed graphs (upper triangular matrices) are also discussed.

Why it matters

OpenAlex reports 295 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

We present a linear-time algorithm for sparse symmetric matrices which converts a matrix into pentadiagonal form (“bandwidth 2”), whenever it is possible to do so using simultaneous row and column permutations. On the other hand when an arbitrary integer k and graph G are given, we show that it is $NP$-complete to determine whether or not there exists an ordering of the vertices such that the adjacency matrix has bandwidth $ \leqq k$, even when G is restircted to the class of free trees with all vertices of degree $ \leqq 3$. Related problems for acyclic directed graphs (upper triangular matrices) are also discussed.

Key concepts: Adjacency matrix, Combinatorics, Mathematics, Adjacency list, Bandwidth (computing), Discrete mathematics, Integer (computer science), Integer matrix

Related papers

Related paper 1Related paper 2Related paper 3
Back to paper searchBrowse research topicsOriginal source
Complexity Results for Bandwidth Minimization — Research Paper | ScholarLens