{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T13:22:07Z","timestamp":1725456127756},"publisher-location":"Berlin\/Heidelberg","reference-count":12,"publisher":"Springer-Verlag","isbn-type":[{"type":"print","value":"354010027X"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/bfb0022521","type":"book-chapter","created":{"date-parts":[[2005,11,23]],"date-time":"2005-11-23T00:49:12Z","timestamp":1132706952000},"page":"414-425","source":"Crossref","is-referenced-by-count":3,"title":["On a subclass of pseudopolynomial problems"],"prefix":"10.1007","author":[{"given":"Burkhard","family":"Monien","sequence":"first","affiliation":[]}],"member":"297","reference":[{"key":"30_CR1","doi-asserted-by":"crossref","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, GDR","DOI":"10.1016\/0304-3975(80)90006-7"},{"key":"30_CR2","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/S0022-0000(74)80027-9","volume":"8","author":"B.S. Baker","year":"1974","unstructured":"Baker, B.S. and R.V. Book, Reversal-bounded multipushdown machines, J. Comp. Syst. Sci. 8 (1974), 315\u2013332","journal-title":"J. Comp. Syst. Sci."},{"key":"30_CR3","volume-title":"Theory of Scheduling","author":"R.W. Conway","year":"1967","unstructured":"Conway, R.W., W.L. Maxwell and L.W. Miller, Theory of Scheduling, Addison-Wesley, Reading, Mass., 1967"},{"key":"30_CR4","doi-asserted-by":"crossref","first-page":"4","DOI":"10.1145\/321623.321625","volume":"18","author":"S.A. Cook","year":"1971","unstructured":"Cook, S.A. Characterizations of Pushdown Machines in Terms of Time-Bounded Computers, J. Ass. Comp. Mach. 18 (1971), 4\u201318","journal-title":"J. Ass. Comp. Mach."},{"key":"30_CR5","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, \u201cStrong\u201d NP-Completeness Results: Motivation, Examples and Implications, J.Ass. Comp. Mach. 25 (1978), 499\u2013508","journal-title":"J.Ass. Comp. Mach."},{"key":"30_CR6","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 Francisco, 1979"},{"key":"30_CR7","unstructured":"Monien, B,. Connections between the LBA problem and the knapsack problem, Proc. Frege-Conference 1979, Jena, GDR"},{"key":"30_CR8","unstructured":"Monien, B., Scheduling problems and space bounded computations, in preparation"},{"key":"30_CR9","unstructured":"Monien, B. and I.H. Sudborough, Bounding the bandwidth of NP-complete problems, in preparation"},{"key":"30_CR10","doi-asserted-by":"crossref","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","DOI":"10.1007\/3-540-08342-1_29"},{"key":"30_CR11","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1145\/321921.321934","volume":"23","author":"S.K. Sahni","year":"1976","unstructured":"Sahni, S.K. Algorithms for Scheduling Independent Tasks, J.Ass. Comp. Mach. 23 (1976), 116\u2013127","journal-title":"J.Ass. Comp. Mach."},{"key":"30_CR12","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"W.J. Savitch","year":"1970","unstructured":"Savitch, W.J., Relationships between nondeterministic and deterministic tape complexities, J. Comp. Syst. Sci. 4(1970), 177\u2013192","journal-title":"J. Comp. Syst. Sci."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1980"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.springerlink.com\/index\/pdf\/10.1007\/BFb0022521","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,11]],"date-time":"2020-04-11T00:21:22Z","timestamp":1586564482000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BFb0022521"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["354010027X"],"references-count":12,"URL":"https:\/\/doi.org\/10.1007\/bfb0022521","relation":{},"subject":[]}}