##
**The bandwidth problem for graphs and matrices - a survey.**
*(English)*
Zbl 0494.05057

### MSC:

05C99 | Graph theory |

05C35 | Extremal problems in graph theory |

05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |

05-02 | Research exposition (monographs, survey articles) pertaining to combinatorics |

Full Text:
DOI

### References:

[1] | Adolfson, SIAM J. Appl. Math. 25 pp 403– (1973) |

[2] | Akhras, Internat. J. Numer. Methods Engrg. 10 pp 787– (1976) |

[3] | Akyuz, J. Amer. Inst. Aeronaut. Astronaut. 7 pp 381– (1969) |

[4] | Akyuz, J. Amer. Inst. Aeronaut. Astronaut. 6 pp 728– (1968) |

[5] | Alway, Comput. J. 8 pp 264– (1965) |

[6] | and , An improved method for reducing the bandwidth of sparse symmetric matrices. In Information Processing 71 (Proc. IFIP Congress 71), North Holland, Amsterdam (1972) 1246–1250. · Zbl 0269.32010 |

[7] | Arany, Informác. Elektron. 4 pp 273– (1973) |

[8] | Barlow, J. Amer. Inst. Aeronaut. Astronaut. 7 pp 380– (1969) |

[9] | Numbered undirected graphs and their uses: A survey of a unifying scientific and engineering concept and its use in developing a theory of nonredundant hemometric sets relating to some ambiguities in X-ray diffraction analysis. Ph.D. dissertation, University of Southern California, Los Angeles (1975). |

[10] | Bloom, Proc. IEEE 65 pp 562– (1977) |

[11] | , and , An empirical investigation of reordering and data management for finite element systems of equations. Argonne Nat. Lab. Report #8056, Argonne, IL (1973). |

[12] | Cheng, Computing 2 pp 103– (1973) |

[13] | Cheng, Computing 2 pp 27– (1973) |

[14] | The bandwidth of the corona and composition of two graphs. MS, Department of Mathematics, Humboldt State University, Arcata, California (1980). |

[15] | The bandwidth and other invariants of the Möbius Ladder. Technical Report, Department of Mathematics, Humboldt State University (1980). |

[16] | Critical bandwidth - 3 trees. Technical Report, Humboldt State University (1980). |

[17] | , and , On the bandwidth of a graph and its complement. The Theory and Applications of Graphs, Ed. Wiley, New York (1981) 243–253. |

[18] | Chvátal, Czechoslovak Math. J. 20 pp 109– (1970) |

[19] | On the bandwidth problem for graphs. Ph.D. dissertation, Department of Combinatorics and Optimization, University of Waterloo (1980). |

[20] | Chvátalová, Discrete Math. 11 pp 249– (1975) |

[21] | , and , The bandwidth problem for graphs: a collection of recent results. Research Report #24, Department of Computer Science, UWO, London, Ontario (1975). |

[22] | and , Two results on the bandwidth of graphs. 10th S. E. Conference on Combinatorics, Graph Theory and Computing 1. Utilitas Mathematica, Winnipeg (1979) 263–274. |

[23] | and , The bandwidth problem and operations on graphs. To appear. · Zbl 0603.05042 |

[24] | Collins, Internat. J. Numer. Methods Engr. 6 pp 345– (1973) |

[25] | Automated input preparation for NASTRAN. Goddard Space Flight Center Report X-321-69-237 (1969). |

[26] | Crane, ACM Trans. Math. Software 2 pp 375– (1976) |

[27] | Crose, J. Dech. Div. ASCE 97 pp 163– (1971) |

[28] | Several strategies for reducing the bandwidth of matrices. In Sparse Matrices and their Applications, and , Eds. Plenum, New York (1972) 157–166. |

[29] | , Reducing the bandwidth of sparse symmetric matrices. Proc. 24th Nat. Conf. ACM (1969) 157–172. |

[30] | The bandwidth problem for graphs: some recent results. In 7th S. E. Conference on Combinatorics, Graph Theory and Computing. Utilitas Mathematica, Winnipeg (1976) 273–288. |

[31] | Tree topology and the NP-completeness of tree bandwidth. Research Report #60, Department of Computer Science, UWO, London, Ontario (1980). |

[32] | The bandwidth of the complete multipartite graph. Presented at the Toledo Symposium on Applications of Graph Theory (1979). |

[33] | Eitner, Abst. Amer. Math. Soc. 1 pp 408– (1980) |

[34] | Epp, J. Hydraulics Div. Proc. ASCE 96 pp 43– (1970) |

[35] | The BANDIT computer program for the reduction of matrix bandwidth for NASTRAN. NSRDC Report 3827, Bethesda, MD (1972). |

[36] | Everstine, Internat. J. Numer. Methods in Engr. 14 pp 837– (1979) |

[37] | Recent improvements to BANDIT. In NASTRAN’s User Experience NASA TM X-3278 (1975) 511–521. |

[38] | FitzGerald, Math. Comput. 28 pp 825– (1974) |

[39] | Fulkerson, Pacific J. Math. 15 pp 835– (1965) · Zbl 0132.21001 |

[40] | Garey, SIAM J. Appl. Math. 34 pp 477– (1978) |

[41] | and , Computers and Intractibility: A Guide to the Theory of NP-Completeness. W. H. Freeman, San Franciso (1979). |

[42] | Garey, Theoretical Comp. Sci. 1 pp 237– (1976) |

[43] | , and , Some simplified NP-complete problems. Proc. 6th Annual ACM Symp. On Theory of Computing (1974) 47–63. |

[44] | Computer Implementation of the finite element method. Ph.D. dissertation, Tech. Report STAN-CS-71-208, Computer Science Department, Stanford University, Stanford, CA (1971). |

[45] | George, SIAM J. Numer. Anal. 15 pp 297– (1978) |

[46] | Gibbs, ACM Trans. Math. Software 2 pp 378– (1976) |

[47] | The bandwidth of graphs. Ph.D. dissertation, Purdue University, Lafayette, IN (1969). |

[48] | Gibbs, Comm. ACM 20 pp 20– (1974) |

[49] | Gibbs, SIAM J. Numer. Anal. 13 pp 235– (1976) |

[50] | , and , An algorithm for reducing the bandwidth and profile of a sparse matrix. ICASE (1974). |

[51] | Gibbs, ACM Trans. Math. Software 2 pp 322– (1976) |

[52] | How to number a graph. Graph Theory and Computing, Ed. Academic, New York (1972) 23–37. |

[53] | Graham, Ann. N.Y. Acad. Sci. 175 pp 170– (1970) · Zbl 0229.05126 |

[54] | Grooms, J. Struct. Div. ASCE 98 pp 203– (1972) |

[55] | Graph Theory. Addison-Wesley, Reading, MA (1969). |

[56] | Problem 16, In Theory of graphs and its applications. Ed., Czechoslovak Academy of Science, Prague (1967). |

[57] | Harper, J. SIAM 12 pp 131– (1964) |

[58] | Harper, J. Combinat. Theory 1 pp 385– (1966) |

[59] | Some unsolved problems involving combinatorial algorithms. MS, Department of Computer and Information Science, University of Oregon (1980). |

[60] | Kahn, Discrete Math. 33 pp 323– (1981) |

[61] | King, Internat. J. Numer. Methods Engr. 2 pp 523– (1970) |

[62] | Konishi, J. Structural Mech. 4 pp 197– (1976) |

[63] | Numberings of the vertices of graphs. Computer Science Department Technical Report 5, Purdue University, Lafayette, IN (1966). |

[64] | and , The bandwidth of cubic graphs. Res. Memo 70-1, School of Industrial Engineering, Purdue University, Lafayette, IN (1970). |

[65] | Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Submitted. · Zbl 0374.68033 |

[66] | and , Relabelling algorithm to obtain a band-matrix from a sparse one. Technical Report PFL-3-72, Department of Civil Engineering, University of Sherbrooke, Sherbrooke, Quebec (1972). |

[67] | Levy, Jet Propul. Lab. Quart. Tech. Rev. 1 pp 61– (1971) |

[68] | Structural stiffness matrix wavefront resequencing program (WAVEFRONT). JPL Technical Report 32–1526, Vol. XIV (1972) 50–55. |

[69] | Lewis, ACM Trans. Math. Software. |

[70] | Bandwidth reduction for simultaneous equations in matrix analysis. Babcock and Wilcox Co., Report TP-535, Lynchburg, VA (1974). |

[71] | On reducing the profile of sparse symmetric matrices. Ph.D. dissertation, Department of Computer Science, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario (1975). |

[72] | Liu, SIAM J. Num. Anal. 12 pp 198– (1975) |

[73] | Livesley, Comput. J. 3 pp 34– (1960) |

[74] | Nelson, J. Structural Div. ASCE 98 pp 2820– (1972) |

[75] | Papadimitriou, Computing 16 pp 263– (1976) |

[76] | Relabelling of finite-element meshes using a random process. NASA Technical Memo. NASA TM X-2660 (1972). |

[77] | Rodrigues, J. Struct. Div. ASCE 101 pp 361– (1975) |

[78] | On certain valuations of the vertices of a graph. Theory of Graphs, International Symposium Rome. Gordon and Breach (1967) 349–355. |

[79] | A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. Graph Theory and Computing, Ed. Academic, New York (1972) 23–37. |

[80] | Matrix bandwidth minimization. Proc. 23rd Natl. Conf. ACM. Brandon Systems, Princeton, NJ (1968) 585–595. |

[81] | Saxe, SIAM J. Albegraic Discrete Methods pp 363– (1980) |

[82] | Sheppard, Discrete Math. 15 pp 379– (1976) |

[83] | and , Another algorithm for reducing bandwidth and profile of a sparse matrix. Proc. AFIPS 1976 NCC, AFIPS Press, Montvale, New Jersey (1976) 987–994. |

[84] | Snay, Bul. Géodésique 50 pp 341– (1976) |

[85] | and , The bandwidth problem for ordered caterpillars. Computer Science Department Report CS-80-065. Washington State University (1980). |

[86] | Tewarson, Comput. J. 10 pp 300– (1967) |

[87] | and , On the bandwidth ordering and isoperimetric problems on graphs that are products of paths or even cycles. To appear. |

[88] | Wang, SIAM J. Appl. Math. 32 pp 860– (1977) |

[89] | Bandwidth minimization, reducibility, decomposition, and triangularization of sparse matrices. Ph.D. dissertation, Department of Computer and Information Science, Ohio State University, Columbus, OH (1973). |

[90] | Wang, SIAM Rev. 17 pp 391– (1975) |

[91] | R. A. Willoughby, Ed., IBM Sparse matrix proceedings. IBM Report RAI, No. 11707 (1969). · Zbl 0181.17003 |

[92] | The bandwidth minimization problem for trees. Master’s thesis, Institute of Computer Science, University of Wroclaw (1980). |

[93] | The Finite Element Method in Engineering Science. McGraw-Hill, London (1971). |

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.