The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
- 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
- https://doi.org/10.1137/0607057
Abstract
No abstract availableKeywords
This publication has 7 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