{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T08:00:48Z","timestamp":1781078448863,"version":"3.54.1"},"reference-count":93,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2006,10,3]],"date-time":"2006-10-03T00:00:00Z","timestamp":1159833600000},"content-version":"vor","delay-in-days":8798,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Journal of Graph Theory"],"published-print":{"date-parts":[[1982,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The bandwidth problem for a graph <jats:italic>G<\/jats:italic> is to label its <jats:italic>n<\/jats:italic> vertices <jats:italic>v<jats:sub>i<\/jats:sub><\/jats:italic> with distinct integers <jats:italic>f<\/jats:italic>(<jats:italic>v<jats:sub>i<\/jats:sub><\/jats:italic>) so that the quantity max{| <jats:italic>f<\/jats:italic>(<jats:italic>v<jats:sub>i<\/jats:sub><\/jats:italic>) \u2212 <jats:italic>f<\/jats:italic>(<jats:italic>v<jats:sub>i<\/jats:sub><\/jats:italic>)| : (<jats:italic>v<jats:sub>i<\/jats:sub> v<jats:sub>j<\/jats:sub><\/jats:italic>) \u2208 <jats:italic>E<\/jats:italic>(<jats:italic>G<\/jats:italic>)} is minimized. The corresponding problem for a real symmetric matrix <jats:italic>M<\/jats:italic> is to find a symmetric permutation <jats:italic>M'<\/jats:italic> of <jats:italic>M<\/jats:italic> so that the quantity max{| <jats:italic>i<\/jats:italic> \u2212 <jats:italic>j<\/jats:italic>| : <jats:italic>m'<jats:sub>ij<\/jats:sub><\/jats:italic> \u2260 0} is minimized. This survey describes all the results known to the authors as of approximately August 1981. These results include the effect on bandwidth of local operations such as refinement and contraction of graphs, bounds on bandwidth in terms of other graph invariants, the bandwidth of special classes of graphs, and approximate bandwidth algorithms for graphs and matrices. The survey concludes with a brief discussion of some problems related to bandwidth.<\/jats:p>","DOI":"10.1002\/jgt.3190060302","type":"journal-article","created":{"date-parts":[[2007,5,29]],"date-time":"2007-05-29T06:49:45Z","timestamp":1180421385000},"page":"223-254","source":"Crossref","is-referenced-by-count":231,"title":["The bandwidth problem for graphs and matrices\u2014a survey"],"prefix":"10.1002","volume":"6","author":[{"given":"P. Z.","family":"Chinn","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J.","family":"Chv\u00e1talov\u00e1","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"A. K.","family":"Dewdney","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"N. E.","family":"Gibbs","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"311","published-online":{"date-parts":[[2006,10,3]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/0125042"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1002\/nme.1620100406"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.2514\/3.55466"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.2514\/3.4575"},{"key":"e_1_2_1_6_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/8.3.264"},{"key":"e_1_2_1_7_2","first-page":"1246","volume-title":"Information Processing 71 (Proc. IFIP Congress 71)","author":"Arany I.","year":"1972"},{"key":"e_1_2_1_8_2","first-page":"273","article-title":"Ritka szimmetrikus matrixok sav\u00e9z\u00e9less\u00e9g redukci\u00f3ja","volume":"4","author":"Arany I.","year":"1973","journal-title":"Inform\u00e1c. Elektron."},{"key":"e_1_2_1_9_2","doi-asserted-by":"publisher","DOI":"10.2514\/3.55465"},{"key":"e_1_2_1_10_2","unstructured":"G. S.Bloom 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\u2010ray diffraction analysis. Ph.D. dissertation University of Southern California Los Angeles (1975)."},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1977.10517"},{"key":"e_1_2_1_12_2","unstructured":"J. H.Bolstad G. K.Leaf A. J.LindemanandG. H.Kaper An empirical investigation of reordering and data management for finite element systems of equations. Argonne Nat. Lab. Report #8056 Argonne IL (1973)."},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02252900"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02239468"},{"key":"e_1_2_1_15_2","volume-title":"MS, Department of Mathematics","author":"Chinn P. Z.","year":"1980"},{"key":"e_1_2_1_16_2","unstructured":"P. Z.Chinn The bandwidth and other invariants of the M\u00f6bius Ladder. Technical Report Department of Mathematics Humboldt State University (1980)."},{"key":"e_1_2_1_17_2","unstructured":"P. Z.Chinn Critical bandwidth \u2010 3 trees. Technical Report Humboldt State University (1980)."},{"key":"e_1_2_1_18_2","first-page":"243","volume-title":"The Theory and Applications of Graphs","author":"Chinn P. Z.","year":"1981"},{"key":"e_1_2_1_19_2","doi-asserted-by":"crossref","first-page":"109","DOI":"10.21136\/CMJ.1970.100949","article-title":"A remark on a problem of Harary","volume":"20","author":"Chv\u00e1tal V.","year":"1970","journal-title":"Czechoslovak Math. J."},{"key":"e_1_2_1_20_2","unstructured":"J.Chv\u00e1talov\u00e1 On the bandwidth problem for graphs. Ph.D. dissertation Department of Combinatorics and Optimization University of Waterloo (1980)."},{"key":"e_1_2_1_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90039-4"},{"key":"e_1_2_1_22_2","unstructured":"J.Chv\u00e1talov\u00e1 A. K.Dewdney N. E.GibbsandR. R.Korfhage The bandwidth problem for graphs: a collection of recent results. Research Report #24 Department of Computer Science UWO London Ontario (1975)."},{"key":"e_1_2_1_23_2","unstructured":"J.Chv\u00e1talov\u00e1andJ.Opatrn\u00fd Two results on the bandwidth of graphs.10th S. E. Conference on Combinatorics Graph Theory and Computing1. Utilitas Mathematica Winnipeg (1979)263\u2013274."},{"key":"e_1_2_1_24_2","unstructured":"J.Chv\u00e1talov\u00e1andJ.Opatrn\u00fd The bandwidth problem and operations on graphs. To appear."},{"key":"e_1_2_1_25_2","doi-asserted-by":"publisher","DOI":"10.1002\/nme.1620060306"},{"key":"e_1_2_1_26_2","unstructured":"W. L.Cook Automated input preparation for NASTRAN. Goddard Space Flight Center Report X\u2010321\u201069\u2010237 (1969)."},{"key":"e_1_2_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/355705.355712"},{"key":"e_1_2_1_28_2","first-page":"163","article-title":"Bandwidth minimization of stiffness matrices","volume":"97","author":"Crose J. G.","year":"1971","journal-title":"J. Dech. Div. ASCE"},{"key":"e_1_2_1_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-8675-3_14"},{"key":"e_1_2_1_30_2","doi-asserted-by":"crossref","unstructured":"E.Cuthill J.McKee Reducing the bandwidth of sparse symmetric matrices.Proc. 24th Nat. Conf. ACM(1969)157\u2013172.","DOI":"10.1145\/800195.805928"},{"key":"e_1_2_1_31_2","unstructured":"A. K.Dewdney The bandwidth problem for graphs: some recent results. In7th S. E. Conference on Combinatorics Graph Theory and Computing.Utilitas Mathematica Winnipeg (1976)273\u2013288."},{"key":"e_1_2_1_32_2","unstructured":"A. K.Dewdney Tree topology and the NP\u2010completeness of tree bandwidth. Research Report #60 Department of Computer Science UWO London Ontario (1980)."},{"key":"e_1_2_1_33_2","unstructured":"P. G.Eitner The bandwidth of the complete multipartite graph. Presented at the Toledo Symposium on Applications of Graph Theory (1979)."},{"key":"e_1_2_1_34_2","first-page":"408","article-title":"The bandwidth problem for directed graphs","volume":"1","author":"Eitner P. G.","year":"1980","journal-title":"Abst. Amer. Math. Soc."},{"key":"e_1_2_1_35_2","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1061\/JYCEAJ.0002316","article-title":"Efficient code for steady\u2010state flows in networks","volume":"96","author":"Epp R.","year":"1970","journal-title":"J. Hydraulics Div. Proc. ASCE"},{"key":"e_1_2_1_36_2","unstructured":"G. C.Everstine The BANDIT computer program for the reduction of matrix bandwidth for NASTRAN. NSRDC Report 3827 Bethesda MD (1972)."},{"key":"e_1_2_1_37_2","doi-asserted-by":"publisher","DOI":"10.1002\/nme.1620140606"},{"key":"e_1_2_1_38_2","unstructured":"G.Everstine Recent improvements to BANDIT. InNASTRAN's User ExperienceNASA TM X\u20103278 (1975)511\u2013521."},{"key":"e_1_2_1_39_2","doi-asserted-by":"publisher","DOI":"10.2307\/2005704"},{"key":"e_1_2_1_40_2","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1965.15.835"},{"key":"e_1_2_1_41_2","doi-asserted-by":"publisher","DOI":"10.1137\/0134037"},{"key":"e_1_2_1_42_2","volume-title":"Computers and Intractibility: A Guide to the Theory of NP\u2010Completeness","author":"Garey M. R.","year":"1979"},{"key":"e_1_2_1_43_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"e_1_2_1_44_2","doi-asserted-by":"crossref","unstructured":"M. R.Garey D. S.Johnson andR. L.Stockmeyer Some simplified NP\u2010complete problems.Proc. 6th Annual ACM Symp. On Theory of Computing(1974)47\u201363.","DOI":"10.1145\/800119.803884"},{"key":"e_1_2_1_45_2","unstructured":"J. A.George Computer Implementation of the finite element method. Ph.D. dissertation Tech. Report STAN\u2010CS\u201071\u2010208 Computer Science Department Stanford University Stanford CA (1971)."},{"key":"e_1_2_1_46_2","doi-asserted-by":"publisher","DOI":"10.1137\/0715021"},{"key":"e_1_2_1_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/355705.355713"},{"key":"e_1_2_1_48_2","unstructured":"N. E.Gibbs The bandwidth of graphs. Ph.D. dissertation Purdue University Lafayette IN (1969)."},{"key":"e_1_2_1_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/360767.360783"},{"key":"e_1_2_1_50_2","doi-asserted-by":"publisher","DOI":"10.1137\/0713023"},{"key":"e_1_2_1_51_2","unstructured":"N. E.Gibbs W. G.PooleJr. andP. K.Stockmeyer An algorithm for reducing the bandwidth and profile of a sparse matrix.ICASE(1974)."},{"key":"e_1_2_1_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/355705.355707"},{"key":"e_1_2_1_53_2","doi-asserted-by":"publisher","DOI":"10.1016\/B978-1-4832-3187-7.50008-8"},{"key":"e_1_2_1_54_2","doi-asserted-by":"publisher","DOI":"10.1111\/j.1749-6632.1970.tb56468.x"},{"key":"e_1_2_1_55_2","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1061\/JSDEAG.0003109","article-title":"Algorithm for matrix bandwidth reduction","volume":"98","author":"Grooms H. R.","year":"1972","journal-title":"J. Struct. Div. ASCE"},{"key":"e_1_2_1_56_2","doi-asserted-by":"publisher","DOI":"10.21236\/AD0705364"},{"key":"e_1_2_1_57_2","volume-title":"Theory of graphs and its applications","author":"Harary F.","year":"1967"},{"key":"e_1_2_1_58_2","doi-asserted-by":"publisher","DOI":"10.1137\/0112012"},{"key":"e_1_2_1_59_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0021-9800(66)80059-5"},{"key":"e_1_2_1_60_2","unstructured":"S. T.Hedetniemi Some unsolved problems involving combinatorial algorithms. MS Department of Computer and Information Science University of Oregon (1980)."},{"key":"e_1_2_1_61_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(81)90276-4"},{"key":"e_1_2_1_62_2","doi-asserted-by":"publisher","DOI":"10.1002\/nme.1620020406"},{"key":"e_1_2_1_63_2","doi-asserted-by":"publisher","DOI":"10.1080\/03601217608907288"},{"key":"e_1_2_1_64_2","unstructured":"R. R.Korfhage Numberings of the vertices of graphs. Computer Science Department Technical Report 5 Purdue University Lafayette IN (1966)."},{"key":"e_1_2_1_65_2","volume-title":"School of Industrial Engineering","author":"Korfhage R. R.","year":"1970"},{"key":"e_1_2_1_66_2","unstructured":"E. L.Lawler Sequencing jobs to minimize total weighted completion time subject to precedence constraints. Submitted."},{"key":"e_1_2_1_67_2","unstructured":"P. F.LemieuxandP. E.Brunelle Relabelling algorithm to obtain a band\u2010matrix from a sparse one. Technical Report PFL\u20103\u201072 Department of Civil Engineering University of Sherbrooke Sherbrooke Quebec (1972)."},{"key":"e_1_2_1_68_2","first-page":"61","article-title":"Resequencing of the structural stiffness matrix to improve computational efficiency","volume":"1","author":"Levy R.","year":"1971","journal-title":"Jet Propul. Lab. Quart. Tech. Rev."},{"key":"e_1_2_1_69_2","unstructured":"R.Levy Structural stiffness matrix wavefront resequencing program (WAVEFRONT). JPL Technical Report 32\u20131526 Vol. XIV (1972)50\u201355."},{"key":"e_1_2_1_70_2","article-title":"Implementation of the Gibbs\u2010Poole\u2010Stockmeyer algorithm and the Gibbs\u2010King algorithm (algorithms 508 and 509)","author":"Lewis J. G.","journal-title":"ACM Trans. Math. Software."},{"key":"e_1_2_1_71_2","unstructured":"C. C.Lin Bandwidth reduction for simultaneous equations in matrix analysis. Babcock and Wilcox Co. Report TP\u2010535 Lynchburg VA (1974)."},{"key":"e_1_2_1_72_2","unstructured":"J. W.Liu On reducing the profile of sparse symmetric matrices. Ph.D. dissertation Department of Computer Science Faculty of Mathematics University of Waterloo Waterloo Ontario (1975)."},{"key":"e_1_2_1_73_2","first-page":"198","article-title":"Comparative analysis of the Cuthill\u2010McKee and the reverse Cuthill\u2010McKee ordering algorithms for sparse matrices","volume":"12","author":"Liu J. W. H.","year":"1975","journal-title":"SIAM J. Num. Anal."},{"key":"e_1_2_1_74_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/3.1.34"},{"key":"e_1_2_1_75_2","doi-asserted-by":"crossref","first-page":"2820","DOI":"10.1061\/JSDEAG.0003409","volume":"98","author":"Nelson M. F.","year":"1972","journal-title":"J. Structural Div. ASCE"},{"key":"e_1_2_1_76_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02280884"},{"key":"e_1_2_1_77_2","unstructured":"E.Roberts Relabelling of finite\u2010element meshes using a random process. NASA Technical Memo. NASA TM X\u20102660 (1972)."},{"key":"e_1_2_1_78_2","doi-asserted-by":"crossref","first-page":"361","DOI":"10.1061\/JSDEAG.0003997","article-title":"Node numbering optimization in structural analysis","volume":"101","author":"Rodrigues J. S. N.","year":"1975","journal-title":"J. Struct. Div. ASCE"},{"key":"e_1_2_1_79_2","unstructured":"A.Rosa On certain valuations of the vertices of a graph.Theory of Graphs International Symposium Rome.Gordon and Breach (1967)349\u2013355."},{"key":"e_1_2_1_80_2","first-page":"23","volume-title":"Graph Theory and Computing","author":"Rose D. J.","year":"1972"},{"key":"e_1_2_1_81_2","doi-asserted-by":"publisher","DOI":"10.1145\/800186.810622"},{"key":"e_1_2_1_82_2","doi-asserted-by":"publisher","DOI":"10.1137\/0601042"},{"key":"e_1_2_1_83_2","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(76)90051-0"},{"key":"e_1_2_1_84_2","doi-asserted-by":"publisher","DOI":"10.1145\/1499799.1499935"},{"key":"e_1_2_1_85_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02521587"},{"key":"e_1_2_1_86_2","volume-title":"Computer Science Department Report CS\u201080\u2010065","author":"Syslo M. M.","year":"1980"},{"key":"e_1_2_1_87_2","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/10.3.300"},{"key":"e_1_2_1_88_2","unstructured":"D. L.WangandP.Wang On the bandwidth ordering and isoperimetric problems on graphs that are products of paths or even cycles. To appear."},{"key":"e_1_2_1_89_2","doi-asserted-by":"publisher","DOI":"10.1137\/0132073"},{"key":"e_1_2_1_90_2","unstructured":"P. T. R.Wang Bandwidth minimization reducibility decomposition and triangularization of sparse matrices. Ph.D. dissertation Department of Computer and Information Science Ohio State University Columbus OH (1973)."},{"key":"e_1_2_1_91_2","first-page":"391","article-title":"Bandwidth reduction of sparse matrices by row and column permutations","volume":"17","author":"Wang P. T. R.","year":"1975","journal-title":"SIAM Rev."},{"key":"e_1_2_1_92_2","unstructured":"R. A. Willoughby Ed. IBM Sparse matrix proceedings. IBM Report RAI No. 11707 (1969)."},{"key":"e_1_2_1_93_2","unstructured":"J. W.Zak The bandwidth minimization problem for trees. Master's thesis Institute of Computer Science University of Wroclaw (1980)."},{"key":"e_1_2_1_94_2","volume-title":"The Finite Element Method in Engineering Science","author":"Zienkiewicz O. C.","year":"1971"}],"container-title":["Journal of Graph Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fjgt.3190060302","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/jgt.3190060302","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,12]],"date-time":"2023-11-12T05:07:41Z","timestamp":1699765661000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/jgt.3190060302"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1982,9]]},"references-count":93,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1982,9]]}},"alternative-id":["10.1002\/jgt.3190060302"],"URL":"https:\/\/doi.org\/10.1002\/jgt.3190060302","archive":["Portico"],"relation":{},"ISSN":["0364-9024","1097-0118"],"issn-type":[{"value":"0364-9024","type":"print"},{"value":"1097-0118","type":"electronic"}],"subject":[],"published":{"date-parts":[[1982,9]]}}}