The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
Author:
- Burkhard MonienBMBurkhard Monien
- 1 October 1986
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Algebraic Discrete Methods
- Vol. 7 (4) , 505-512
Abstract
It is shown that the Bandwidth Minimization problem remains NP-complete even when restricted to “caterpillars with hairs of length at most three”. “Caterpillars” are special trees; they consist of a simple chain (the “body”) with various simple chains attached to thee vertices of the body (the attached chains are called “hairs”). A previous result in the literature shows that the bandwidth of caterpillars with hairs of length at most 2 can be found in $O( n\log n )$ time (this Journal, 2 (1981), pp. 387–393). We also show that the bandwidth problem is NP-complete when restricted to caterpillars with at most one hair attached to each vertex of the body. The proof is relatively straightforward and thereby also provides an easier proof than found in (SIAM J. Appl. Math., 34 (1978), pp. 477–495) that the bandwidth problem is NP-complete for trees with maximum vertex degree 3.
Keywords
This publication has 8 references indexed in Scilit:
- Improved dynamic programming algorithms for bandwidth minimization and the MinCut Linear Arrangement problemJournal of Algorithms, 1984
- The bandwidth problem for graphs and matrices—a surveyJournal of Graph Theory, 1982
- The Bandwidth of Caterpillars with Hairs of Length 1 and 2SIAM Journal on Algebraic Discrete Methods, 1981
- Dynamic-Programming Algorithms for Recognizing Small-Bandwidth Graphs in Polynomial TimeSIAM Journal on Algebraic Discrete Methods, 1980
- Complexity Results for Bandwidth MinimizationSIAM Journal on Applied Mathematics, 1978
- The NP-Completeness of the bandwidth minimization problemComputing, 1976
- Comparative Analysis of the Cuthill–McKee and the Reverse Cuthill–McKee Ordering Algorithms for Sparse MatricesSIAM Journal on Numerical Analysis, 1976
- Reducing the bandwidth of sparse symmetric matrices1969