The NP-completeness of the bandwidth minimization problem. (English) Zbl 0321.65019


65F05 Direct numerical methods for linear systems and matrix inversion
15A15 Determinants, permanents, traces, other special matrix functions
05C99 Graph theory
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI


[1] Cuthill, E., McKee, J.: Reducing the Bandwidth of Sparse Symmetric Matrices. Proc. 24-th Nat. Conf. ACM, pp. 157–172 (1969).
[2] Cuthill, E.: Several Strategies for Reducing the Bandwidth of Matrices, in: Sparse Matrices and their Applications (Rose, D., Willoughby, R., eds.). Plenum Press 1972.
[3] Tewarson, R. P.: Sparse Matrices. Chapter 3.8. Academic Press 1973. · Zbl 0262.65021
[4] Chen, K. Y.: Minimizing the Bandwidth of Sparse Symmetric Matrices. Computing11, 103–110 (1973). · Zbl 0263.65049
[5] Chen, K. Y.: Note on Minimizing the Bandwidth of Sparse Symmetric Matrices. Computing11, 27–30 (1973). · Zbl 0257.65041
[6] Harary, F.: Sparse Matrices in Graph Theory, in: Large Sparse Sets of Linear Equations (Reidl, J. K., ed.), pp. 139–150. Academic Press 1970.
[7] Karp, R. M.: Reducibility among Combinatorial Problems, in: Complexity of Computer Computations (Miller, R., Thatcher, J., eds.). Plenum Press 1972. · Zbl 0366.68041
[8] Aho, A. V., Hopcroft, J. E., Ullman, J. D.: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974. · Zbl 0326.68005
[9] Sahni, S., Gonzalez, T.: P-Complete Problems and Approximate Solutions. Proc. 15th SWAT Symposium, 1974.
[10] Garey, M. R., Johnson, D. S., Stockmeyer, L.: Some Simplified NP-Complete Problems. Proc. 6th Annual ACM Symposium on Theory of Computing, pp. 47–63 (1974). · Zbl 0338.05120
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.