{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:48:48Z","timestamp":1725662928317},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540108566"},{"type":"electronic","value":"9783540387695"}],"license":[{"start":{"date-parts":[[1981,1,1]],"date-time":"1981-01-01T00:00:00Z","timestamp":347155200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1981]]},"DOI":"10.1007\/3-540-10856-4_75","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T12:34:22Z","timestamp":1330173262000},"page":"78-93","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Time and space bounded complexity classes and bandwidth constrained problems"],"prefix":"10.1007","author":[{"given":"Burkhard","family":"Monien","sequence":"first","affiliation":[]},{"given":"Ivan Hal","family":"Sudborough","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"issue":"1","key":"6_CR1","doi-asserted-by":"crossref","first-page":"114","DOI":"10.1145\/322234.322243","volume":"28","author":"A. K. Chandra","year":"1981","unstructured":"A. K. Chandra, D. C. Kozen, and L. J. Stockmeyer, Alternation, J. ACM 28,1 (1981), pp. 114\u2013133.","journal-title":"J. ACM"},{"key":"6_CR2","volume-title":"Some Additional Examples of Bandwidth Constrained NP-Complete Problems","author":"M-J Chung","year":"1981","unstructured":"M-J Chung, W. M. Evangelist, and I. H. Sudborough, Some Additional Examples of Bandwidth Constrained NP-Complete Problems, Proc. 15th Conf. on Information Sciences and Systems (1981), The Johns Hopkins University, Baltimore, Md., U.S.A., to appear."},{"key":"6_CR3","first-page":"151","volume-title":"The Complexity of Theorem-Proving Procedures","author":"S. A. Cook","year":"1971","unstructured":"S. A. Cook, The Complexity of Theorem-Proving Procedures, Proc. 3rd Annual ACM Theory of Computing Symp. (1971), Assoc. for Comput. Mach., New York, pp. 151\u2013158."},{"key":"6_CR4","first-page":"338","volume-title":"Deterministic CFL's are Accepted Simultaneously in Polynomial Time and Log Squared Space","author":"S. A. Cook","year":"1979","unstructured":"S. A. Cook, Deterministic CFL's are Accepted Simultaneously in Polynomial Time and Log Squared Space, Proc. 11th Annual ACM Theory of Computing Symp. (1979), Assoc. for Comput. Mach., New York, pp. 338\u2013345."},{"key":"6_CR5","series-title":"Tech. Report","volume-title":"Towards a Complexity Theory of Synchronous Parallel Computation","author":"S. A. Cook","year":"1980","unstructured":"S. A. Cook, Towards a Complexity Theory of Synchronous Parallel Computation, Tech. Report #141\/80 (1980), Dept. of Computer Science, University of Toronto, Toronto, Canada."},{"issue":"4","key":"6_CR6","doi-asserted-by":"crossref","first-page":"710","DOI":"10.1145\/321978.321989","volume":"23","author":"S. Even","year":"1976","unstructured":"S. Even and R. E. Tarjan, A Combinatorial Problem which is Complete in Polynomial Space, J. ACM 23,4 (1976), pp. 710\u2013719.","journal-title":"J. ACM"},{"key":"6_CR7","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","volume":"1","author":"M. R. Garey","year":"1976","unstructured":"M. R. Garey, D. S. Johnson, and L. Stockmeyer, Some Simplified NP-Complete Graph Problems, Theoretical Computer Science 1 (1976), pp. 237\u2013267.","journal-title":"Theoretical Computer Science"},{"key":"6_CR8","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1137\/0134037","volume":"34","author":"M. R. Garey","year":"1978","unstructured":"M. R. Garey, R. L. Graham, D. S. Johnson, and D. E. Knuth, Complexity Results for Bandwidth Minimization, SIAM J. Appl. Math. 34 (1978), pp. 477\u2013495.","journal-title":"SIAM J. Appl. Math."},{"key":"6_CR9","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. R. Garey","year":"1979","unstructured":"M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman and Co., San Francisco, 1979."},{"issue":"3","key":"6_CR10","doi-asserted-by":"crossref","first-page":"513","DOI":"10.1137\/0209038","volume":"9","author":"J. R. Gilbert","year":"1980","unstructured":"J. R. Gilbert, T. Lengauer, and R. E. Tarjan, The Pebbling Problem is Complete in Polynomial Space, SIAM J. Comput. 9,3 (1980), pp. 513\u2013524.","journal-title":"SIAM J. Comput."},{"key":"6_CR11","volume-title":"Introduction to Automata Theory, Languages, and Computation","author":"J. E. Hopcroft","year":"1979","unstructured":"J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing Co., Reading, Mass., U.S.A., 1979."},{"key":"6_CR12","first-page":"337","volume-title":"Length of Predicate Calculus Formulas as a new Complexity Measure","author":"N. Immerman","year":"1979","unstructured":"N. Immerman, Length of Predicate Calculus Formulas as a new Complexity Measure, Proc. 20th Annual Symp. on Foundations of Computer Sci. (1979), IEEE Computer Society, Long Beach, Calif., U.S.A., pp. 337\u2013347."},{"key":"6_CR13","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1016\/S0022-0000(75)80050-X","volume":"11","author":"N. D. Jones","year":"1975","unstructured":"N. D. Jones, Space Bounded Reducibility Among Combinatorial Problems, J. Comput. System Sci. 11 (1975), pp. 68\u201385.","journal-title":"J. Comput. System Sci."},{"key":"6_CR14","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"R. M. Karp","year":"1972","unstructured":"R. M. Karp, Reducibility Among Combinatorial Problems, in R. E. Miller and J. W. Thatcher (eds.), Complexity of Computer Computations, Plenum Press, New York, 1972, pp. 85\u2013103."},{"issue":"1","key":"6_CR15","doi-asserted-by":"crossref","first-page":"18","DOI":"10.1145\/990518.990519","volume":"7","author":"R. E. Ladner","year":"1975","unstructured":"R. E. Ladner, The Circuit Value Problem is Log Space Complete for P, SIGACT News 7,1 (1975), pp. 18\u201320.","journal-title":"SIGACT News"},{"key":"6_CR16","unstructured":"B. Monien and I. H. Sudborough, On Eliminating Nondeterminism from Turing Machines which use less than Logarithm Worktape Space, in Vol. 72 Lecture Notes in Computer Science, Springer Verlag (1979), pp. 431\u2013445."},{"key":"6_CR17","volume-title":"Bandwidth Constrained NP-Complete Problems","author":"B. Monien","year":"1981","unstructured":"B. Monien and I. H. Sudborough, Bandwidth Constrained NP-Complete Problems, Proc. 13th Annual ACM Theory of Computing Symp. (1981), Assoc. for Comput. Mach., New York, to appear."},{"key":"6_CR18","volume-title":"Bandwidth Problems in Graphs","author":"B. Monien","year":"1980","unstructured":"B. Monien and I. H. Sudborough, Bandwidth Problems in Graphs, Proc. 18th Annual Allerton Conference on Communication, Control, and Computing (1980), Dept. of Computer Science, University of Illinois, Champaign-Urbana, Illinois, U.S.A., to appear."},{"key":"6_CR19","unstructured":"B. Monien, private communication."},{"key":"6_CR20","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/BF02280884","volume":"16","author":"C. H. Papadimitriou","year":"1976","unstructured":"C. H. Papadimitriou, The NP-Completeness of the Bandwidth Minimization Problem, Computing 16 (1976), pp. 263\u2013270.","journal-title":"Computing"},{"key":"6_CR21","first-page":"307","volume-title":"Proc. 20th Annual Symp. on Foundations of Computer Sci.","author":"N. Pippenger","year":"1979","unstructured":"N. Pippenger, On Simultaneous Resource Bounds, Proc. 20th Annual Symp. on Foundations of Computer Sci. (1979), IEEE Computer Society, Long Beach, Calif., U.S.A., pp. 307\u2013311."},{"key":"6_CR22","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W. J. Savitch","year":"1970","unstructured":"W. J. Savitch, Relationships between Nondeterministic and Deterministic Tape Complexities, J. Comput. and System Sci. 4 (1970), pp. 177\u2013192.","journal-title":"J. Comput. and System Sci."},{"key":"6_CR23","volume-title":"Dynamic-Programming Algorithms for Recognizing Small Bandwidth Graphs in Polynomial Time","author":"J. B. Saxe","year":"1979","unstructured":"J. B. Saxe, Dynamic-Programming Algorithms for Recognizing Small Bandwidth Graphs in Polynomial Time, Proc. 17th Annual Allerton Conference on Communication, Control, and Computing (1979), Dept. of Computer Science, University of Illinois, Champaign-Urbana, Illinois, U.S.A."},{"key":"6_CR24","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/0022-0000(78)90045-4","volume":"16","author":"T. J. Schaefer","year":"1978","unstructured":"T. J. Schaefer, Complexity of Some Two-Person Perfect-Information Games, J. Comput. System Sci. 16 (1978), pp. 185\u2013225.","journal-title":"J. Comput. System Sci."},{"key":"6_CR25","first-page":"62","volume-title":"Efficient Algorithms for Path System Problems and Applications to Alternating and Time-Space Complexity Classes","author":"I. H. Sudborough","year":"1980","unstructured":"I. H. Sudborough, Efficient Algorithms for Path System Problems and Applications to Alternating and Time-Space Complexity Classes, Proc. 21st Annual Symp. on Foundations of Computer Sci. (1980), IEEE Computer Society, Long Beach, Calif., U.S.A., pp. 62\u201373."},{"key":"6_CR26","doi-asserted-by":"crossref","unstructured":"I. H. Sudborough, Pebbling and Bandwidth, Proc. Fundamentals of Computation Theory Symp. (1981), to appear in Springer Verlag Lecture Notes in Computer Science series.","DOI":"10.1007\/3-540-10854-8_41"},{"key":"6_CR27","unstructured":"O. Vornberger, Komplexit\u00e4t von Wegeproblemen in Graphen, Ph.D. dissertation, Fachbereich Mathematik\/Informatik, Universit\u00e4t Paderborn, Paderborn, West Germany."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1981"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-10856-4_75","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,1,8]],"date-time":"2020-01-08T18:29:41Z","timestamp":1578508181000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-10856-4_75"}},"subtitle":["A survey"],"short-title":[],"issued":{"date-parts":[[1981]]},"ISBN":["9783540108566","9783540387695"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/3-540-10856-4_75","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1981]]},"assertion":[{"value":"3 June 2005","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}