The NP-Completeness of the bandwidth minimization problem

Cuthill, E., McKee, J.: Reducing the Bandwidth of Sparse Symmetric Matrices. Proc. 24-th Nat. Conf. ACM, pp. 157–172 (1969).

Cuthill, E.: Several Strategies for Reducing the Bandwidth of Matrices, in: Sparse Matrices and their Applications (Rose, D., Willoughby, R., eds.). Plenum Press 1972.

Tewarson, R. P.: Sparse Matrices. Chapter 3.8. Academic Press 1973.

Chen, K. Y.: Minimizing the Bandwidth of Sparse Symmetric Matrices. Computing11, 103–110 (1973).

Chen, K. Y.: Note on Minimizing the Bandwidth of Sparse Symmetric Matrices. Computing11, 27–30 (1973).

Harary, F.: Sparse Matrices in Graph Theory, in: Large Sparse Sets of Linear Equations (Reidl, J. K., ed.), pp. 139–150. Academic Press 1970.

Karp, R. M.: Reducibility among Combinatorial Problems, in: Complexity of Computer Computations (Miller, R., Thatcher, J., eds.). Plenum Press 1972.

Aho, A. V., Hopcroft, J. E., Ullman, J. D.: The Design and Analysis of Computer Algorithms. Addison-Wesley 1974.

Sahni, S., Gonzalez, T.: P-Complete Problems and Approximate Solutions. Proc. 15th SWAT Symposium, 1974.

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).