{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T14:46:22Z","timestamp":1770993982747,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":15,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540102915","type":"print"},{"value":"9783540384359","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1981]]},"DOI":"10.1007\/3-540-10291-4_20","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T12:09:38Z","timestamp":1330171778000},"page":"279-292","source":"Crossref","is-referenced-by-count":7,"title":["Bounding the bandwidth of NP-complete problems"],"prefix":"10.1007","author":[{"given":"Burkhard","family":"Monien","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ivan Hal","family":"Sudborough","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,25]]},"reference":[{"key":"20_CR1","volume-title":"The design and analysis of computer algorithms","author":"A. V. Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E. and J.D. Ullman, The design and analysis of computer algorithms, Addison-Wesley, Reading Mass., 1974"},{"key":"20_CR2","unstructured":"Ausiello, G., A. Marchetti-Spaccamela and M. Protasi, Toward a unified approach for the classification of NP-complete optimization problems, Proc.Frege-Conference 1979, Jena, DDR, 43\u201361"},{"key":"20_CR3","doi-asserted-by":"crossref","unstructured":"Cook, S.A., The complexity of theorem-proving procedures, Proc. of 1971 ACM Theory of Computing Conference, 151\u2013158","DOI":"10.1145\/800157.805047"},{"key":"20_CR4","doi-asserted-by":"crossref","first-page":"499","DOI":"10.1145\/322077.322090","volume":"25","author":"M. R. Garey","year":"1978","unstructured":"Garey, M.R. and D.S. Johnson, \"Strong\" NP-Completeness Results: Motivation, Examples and Implications, J.Ass.Comp. Mach 25(1978),499\u2013508","journal-title":"J.Ass.Comp. Mach"},{"key":"20_CR5","volume-title":"Computers and Intractability, A Guide to the Theory of NP-completeness","author":"M. R. Garey","year":"1979","unstructured":"Garey, M.R. and D.S. Johnson, Computers and Intractability, A Guide to the Theory of NP-completeness, W.H.Freeman and Company, San Franzisco, 1979"},{"key":"20_CR6","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M. R. Garey","year":"1976","unstructured":"Garey, M.R., Johnson, D.S. and L. Stockmeyer, Some simplified NP-complete graph problems, Theor. Comp. Sci. 1(1976), 237\u2013267","journal-title":"Theor. Comp. Sci."},{"key":"20_CR7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/BF01683259","volume":"10","author":"N. D. Jones","year":"1976","unstructured":"Jones, N.D., Lien, Y.E. and W.T. Laaser, New problems complete for nondeterministic log space, Math. Syst. Th. 10 (1976), 1\u201317","journal-title":"Math. Syst. Th."},{"key":"20_CR8","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Reducibility among combinatorial problems, in Complexity of Computer Computation","author":"R. M. Karp","year":"1972","unstructured":"Karp, R.M., Reducibility among combinatorial problems, in Complexity of Computer Computation, Ed. Miller, Thatcher, Plenum Press 1972, 85\u2013103"},{"key":"20_CR9","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1287\/opre.26.1.22","volume":"26","author":"J. K. Lenstra","year":"1978","unstructured":"Lenstra, J.K. and A.H.G. Rinnoy Kan, Complexity of Scheduling under Precedence Constraints, Operations Research 26 (1978), 22\u201335","journal-title":"Operations Research"},{"key":"20_CR10","doi-asserted-by":"crossref","unstructured":"Monien, B., On a subclass of pseudopolynomial problems, Proc. 8th Symp. on Math. Found. of Comp. Sci., Rydzyna-Zamek, Poland","DOI":"10.1007\/BFb0022521"},{"key":"20_CR11","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/BF02280884","volume":"16","author":"Ch. H. Papadimitrion","year":"1976","unstructured":"Papadimitrion, Ch. H., The NP-completeness of the bandwidth minimization problem, Computing 16 (1976), 263\u2013270","journal-title":"Computing"},{"key":"20_CR12","doi-asserted-by":"crossref","first-page":"370","DOI":"10.1007\/3-540-08342-1_29","volume":"52","author":"A. Paz","year":"1977","unstructured":"Paz, A. and S. Moran, Non-deterministic polynomial optimization problems and their approximation, Lecture Notes Comp.Sci. 52, 370\u2013379, Springer-Verlag,Berlin-Heidelberg-New York, 1977","journal-title":"Lecture Notes Comp.Sci."},{"key":"20_CR13","unstructured":"Saxe, J.B., Dynamic Programming algorithms for recognizing small-bandwidth graphs in polynomial time, Technicel Report, Comp.Sci.Dept., Carnegie Mellon University, Pittsburgh"},{"key":"20_CR14","doi-asserted-by":"crossref","unstructured":"Sudborough, I.H., Efficient algorithms for path system problems and applications to alternating and time-space complexity classes, Proc. of 1980 IEEE FOCS conference","DOI":"10.1109\/SFCS.1980.17"},{"key":"20_CR15","unstructured":"Vornberger, O., Komplexit\u00e4t von Wegeproblemen in Graphen, Bericht Nr. 5\/79, Theoret.Inf., Fachbereich Mathe\/Inf.,GH.Paderborn"}],"container-title":["Lecture Notes in Computer Science","Graphtheoretic Concepts in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-10291-4_20.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,27]],"date-time":"2021-04-27T16:36:53Z","timestamp":1619541413000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-10291-4_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981]]},"ISBN":["9783540102915","9783540384359"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/3-540-10291-4_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[1981]]}}}