{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,19]],"date-time":"2025-03-19T14:31:56Z","timestamp":1742394716859},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[1983,6,1]],"date-time":"1983-06-01T00:00:00Z","timestamp":423273600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Computing"],"published-print":{"date-parts":[[1983,6]]},"DOI":"10.1007\/bf02259908","type":"journal-article","created":{"date-parts":[[2005,11,22]],"date-time":"2005-11-22T19:04:21Z","timestamp":1132686261000},"page":"115-139","source":"Crossref","is-referenced-by-count":19,"title":["Bandwidth and pebbling"],"prefix":"10.1007","volume":"31","author":[{"given":"A. L.","family":"Rosenberg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"I. H.","family":"Sudborough","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"BF02259908_CR1","first-page":"728","volume":"6","author":"F. A. Aykuz","year":"1968","unstructured":"Aykuz, F. A., Tuku, S.: An automatic node-relabelling scheme for bandwidth minimization of stiffness matrices. Amer. Inst. of Aero. and Astro. J.6, 728\u2013730 (1968).","journal-title":"Amer. Inst. of Aero. and Astro. J."},{"key":"BF02259908_CR2","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/BF02239468","volume":"11","author":"K. Y. Chen","year":"1973","unstructured":"Chen, K. Y.: Minimizing the bandwidth of sparse symmetric matrices. Computing11, 27\u201330 (1973).","journal-title":"Computing"},{"key":"BF02259908_CR3","doi-asserted-by":"crossref","first-page":"308","DOI":"10.1016\/S0022-0000(74)80046-2","volume":"9","author":"S. A. Cook","year":"1974","unstructured":"Cook, S. A.: An observation on time-space tradeoffs. J. Comp. Syst. Sci.9, 308\u2013316 (1974).","journal-title":"J. Comp. Syst. Sci."},{"key":"BF02259908_CR4","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1137\/0134037","volume":"34","author":"M. R. Garey","year":"1978","unstructured":"Garey, M. R., Graham, R. L., Johnson, D. S., Knuth, D. E.: Complexity results for bandwidth minimization. SIAM J. Appl. Math.34, 477\u2013495 (1978).","journal-title":"SIAM J. Appl. Math."},{"key":"BF02259908_CR5","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1137\/0209038","volume":"9","author":"J. R. Gilbert","year":"1980","unstructured":"Gilbert, J. R., Lengauer, T., Tarjan, R. E.: The pebbling problem is complete in polynomial space. SIAM J. Comput.9, 513\u2013524 (1980).","journal-title":"SIAM J. Comput."},{"key":"BF02259908_CR6","doi-asserted-by":"crossref","first-page":"332","DOI":"10.1145\/322003.322015","volume":"24","author":"J. E. Hopcroft","year":"1977","unstructured":"Hopcroft, J. E., Paul, W., Valiant, L. G.: On time versus space. J. Assoc. Comput. Math.24, 332\u2013337 (1977).","journal-title":"J. Assoc. Comput. Math."},{"key":"BF02259908_CR7","first-page":"423","volume-title":"High Speed Computer and Algorithm Optimization","author":"H. T. Kung","year":"1977","unstructured":"Kung, H. T., Stevenson, D.: A software technique for reducing the routing time on a parallel computer with a fixed interconnection network. In: High Speed Computer and Algorithm Optimization, pp. 423\u2013433. New York: Academic Press 1977."},{"key":"BF02259908_CR8","unstructured":"Lengauer, T.: Relationships between pebble games on directed and undirected graphs. Typescript, 1980."},{"key":"BF02259908_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"300","DOI":"10.1007\/3-540-08860-1_22","volume-title":"AP-space complete problem related to a pebble game","author":"A. Lingas","year":"1978","unstructured":"Lingas, A.: AP-space complete problem related to a pebble game. Lecture Notes in Computer Science62, pp. 300\u2013321. Berlin-Heidelberg-New York: Springer 1978."},{"key":"BF02259908_CR10","doi-asserted-by":"crossref","first-page":"720","DOI":"10.1145\/321978.321990","volume":"23","author":"R. J. Lipton","year":"1976","unstructured":"Lipton, R. J., Eisenstat, S. C., DeMillo, R. A.: Space and time hierarchies for classes of control structures and data structures. J. ACM23, 720\u2013732 (1976).","journal-title":"J. ACM"},{"key":"BF02259908_CR11","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/S0304-3975(81)80004-7","volume":"13","author":"F. Meyer auf der Heide","year":"1981","unstructured":"Meyer auf der Heide, F.: A comparison of two variations of a pebble game on graphs. Theor. Comp. Sci.13, 315\u2013322 (1981).","journal-title":"Theor. Comp. Sci."},{"key":"BF02259908_CR12","unstructured":"Monien, B., Sudborough, I. H.: Bandwidth problems in graphs. Proc. 1980 Allerton Conf. on Communication, Control, and Computing1980, 650\u2013659."},{"key":"BF02259908_CR13","unstructured":"Monien, B., Sudborough, I. H.: Bandwidth constrained NP-complete problems. Proc. 1981 ACM Symp. on Theory of Computing, Milwaukee, Wisc., pp. 207\u2013217."},{"key":"BF02259908_CR14","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/BF02280884","volume":"16","author":"Ch. H. Papadimitriou","year":"1976","unstructured":"Papadimitriou, Ch. H.: The NP-completeness of the bandwidth minimization problem. Computing16, 263\u2013270 (1976).","journal-title":"Computing"},{"key":"BF02259908_CR15","unstructured":"Paterson, M. S., Hewitt, C. E.: Comparative schematology. Proc. Proj. MAC Conf. on Concurrent Systems and Parallel Computation, 1970, pp. 119\u2013127."},{"key":"BF02259908_CR16","unstructured":"Pippenger, N.: Pebbling. In: Proc. 5th IBM Symp. on Mathematical Foundations of Computer Science, 1980."},{"key":"BF02259908_CR17","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/B978-1-4832-3187-7.50018-0","volume-title":"Graph Theory and Computing","author":"D. J. Rose","year":"1972","unstructured":"Rose, D. J.: A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations. In: Graph Theory and Computing (Read, R., ed.), pp. 183\u2013217. New York: Academic Press 1972."},{"key":"BF02259908_CR18","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1007\/BF00288886","volume":"9","author":"A. L. Rosenberg","year":"1978","unstructured":"Rosenberg, A. L.: Data encodings and their costs. Acta Inform.9, 273\u2013292 (1978).","journal-title":"Acta Inform."},{"key":"BF02259908_CR19","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1007\/BF01776564","volume":"12","author":"A. L. Rosenberg","year":"1978","unstructured":"Rosenberg, A. L., Snyder, L.: Bounds on the costs of data encodings. Math. Syst. Th.12, 9\u201339 (1978).","journal-title":"Math. Syst. Th."},{"key":"BF02259908_CR20","unstructured":"Saxe, J. B.: Dynamic-programming algorithms for recognizing small-bandwidth graphs in polynomial time. Carnegie-Mellon Tech. Rpt. CMU-CS-80-102, 1980."},{"key":"BF02259908_CR21","doi-asserted-by":"crossref","first-page":"226","DOI":"10.1137\/0204020","volume":"4","author":"R. Sethi","year":"1975","unstructured":"Sethi, R.: Complete register allocation problems. SIAM J. Comput.4, 226\u2013248 (1975)","journal-title":"SIAM J. Comput."},{"key":"BF02259908_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/3-540-10854-8_41","volume-title":"Fundamentals of Computation Theory","author":"I. H. Sudborough","year":"1981","unstructured":"Sudborough, I. H.: Pebbling and bandwidth. In: Fundamentals of Computation Theory (Lecture Notes in Computer Science, Vol. 117), pp. 373\u2013383. Berlin-Heidelberg-New York: Springer 1981."}],"container-title":["Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02259908.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02259908\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02259908","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,16]],"date-time":"2019-05-16T11:08:14Z","timestamp":1558004894000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02259908"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1983,6]]},"references-count":22,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1983,6]]}},"alternative-id":["BF02259908"],"URL":"https:\/\/doi.org\/10.1007\/bf02259908","relation":{},"ISSN":["0010-485X","1436-5057"],"issn-type":[{"value":"0010-485X","type":"print"},{"value":"1436-5057","type":"electronic"}],"subject":[],"published":{"date-parts":[[1983,6]]}}}