{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T20:40:23Z","timestamp":1742589623323,"version":"3.40.2"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540102915"},{"type":"electronic","value":"9783540384359"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1981]]},"DOI":"10.1007\/3-540-10291-4_21","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T17:09:33Z","timestamp":1330189773000},"page":"293-305","source":"Crossref","is-referenced-by-count":1,"title":["The complexity of path problems in graphs and path systems of bounded bandwidth"],"prefix":"10.1007","author":[{"given":"I. H.","family":"Sudborough","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2005,5,25]]},"reference":[{"key":"21_CR1","doi-asserted-by":"crossref","unstructured":"Aleliunas, R., R.M. Karp, R.J. Lipton, L.Lovasz, C. Rackoff, Random walks, universal sequences, and the complexity of maze problems, Proceedings 1979 IEEE Foundations of Computer Science Conference.","DOI":"10.1109\/SFCS.1979.34"},{"key":"21_CR2","unstructured":"Chandra, A.K., D. Kozen, L.J. Stockmeyer, Alternation, Technical Report RC 7489 (# 32286), IBM T.J. Watson Research Center, Yorktown Heights, New York."},{"key":"21_CR3","doi-asserted-by":"crossref","unstructured":"Cook, S.A., Path systems and language recognition, 1970 ACM Symp. Theory of Computing, 70\u201372.","DOI":"10.1145\/800161.805151"},{"key":"21_CR4","doi-asserted-by":"crossref","unstructured":"\u2014, An observation on time-storage trade-off, J. Computer System Sci. (1974), 308\u2013316.","DOI":"10.1016\/S0022-0000(74)80046-2"},{"key":"21_CR5","doi-asserted-by":"crossref","unstructured":"\u2014, Deterministic CFLs are accepted simultaneously in polynomial time and log squared space, 1979 ACM Symp. Theory of Computing, 338\u2013345.","DOI":"10.1145\/800135.804426"},{"key":"21_CR6","unstructured":"\u2014, Towards a complexity theory of synchronous parallel computation, Technical Report # 141\/80, University of Toronto, Canada."},{"key":"21_CR7","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/S0022-0000(76)80048-7","volume":"13","author":"S. A. Cook","year":"1976","unstructured":"Cook, S.A. and R. Sethi, Storage requirements for deterministic polynomial time recognizable languages, J. Computer System Sci, 13 (1976), 25\u201337.","journal-title":"J. Computer System Sci"},{"key":"21_CR8","doi-asserted-by":"crossref","unstructured":"Garey, M.R., R.L. Graham, D.S. Johnson, and D.E. Knuth, Complexity results for bandwidth minimization, SIAM J. Appl. Math. (May 1978), 477\u2013495.","DOI":"10.1137\/0134037"},{"key":"21_CR9","doi-asserted-by":"crossref","unstructured":"Gilbert, J.R., T. Lengauer, R.E. Tarjan, The pebbling problem is complete in polynomial space, 1979 ACM Symp. Theory of Computing, 237\u2013248.","DOI":"10.1145\/800135.804418"},{"key":"21_CR10","unstructured":"Immerman, N. Length of predicate calculus formulas as a new complexity measure, Proc. 1979 IEEE FOCS, 337\u2013347."},{"key":"21_CR11","doi-asserted-by":"crossref","unstructured":"Lewis, H., and C.H. Papadimitriou, Symmetric space bounded Computation, Proceedings of 1980 ICALP Conference, Lecture Notes in Computer Sience Vd. 85, Springer-Verlag, pp. 374\u2013384.","DOI":"10.1007\/3-540-10003-2_85"},{"key":"21_CR12","doi-asserted-by":"crossref","unstructured":"Lingas, A., A P-Space complete problem related to a pebble game, 1978 ICALP Proceedings, Vol. 62, Lecture Notes in Computer Science, Springer-Verlag, 300\u2013321.","DOI":"10.1007\/3-540-08860-1_22"},{"key":"21_CR13","doi-asserted-by":"crossref","unstructured":"Monien, B. and I.H. Sudborough, Eliminating nondeterminism from Turing machines which use less than logarithm worktape space, 1979 ICALP Proceedings, Vol. 72, Lecture Notes in Computer Science, Springer-Verlag, 431\u2013445.","DOI":"10.1007\/3-540-09510-1_34"},{"key":"21_CR14","doi-asserted-by":"crossref","unstructured":"Monien, B., and I.H. Sudborough, Bounding the bandwidth of NP-complete problems, Proceedings of Workshop on Graph Theoretic Concepts in Computer Science, Bad Honnef\/Bonn, June 15\u201318, 1980.","DOI":"10.1007\/3-540-10291-4_20"},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., The NP-completeness of the bandwidth minimization problem, Computing (1976), 263\u2013270.","DOI":"10.1007\/BF02280884"},{"key":"21_CR16","doi-asserted-by":"crossref","unstructured":"Savitch, W.J., Relationship between nondeterministic and deterministic tape complexities, J. Computer System Sci. (1970), 177\u2013192.","DOI":"10.1016\/S0022-0000(70)80006-X"},{"key":"21_CR17","unstructured":"Saxe, J.B., Dynamic-Programming algorithms for recognizing small-bandwidth graphs in polynomial time, Technical Report, Computer Science Dept. Carnegie Mellon University, Pittsburgh, Pennsylvania."},{"key":"21_CR18","doi-asserted-by":"crossref","unstructured":"Sudborough, I.H., Efficient algorithms for path system problems and applications to alternating and time-space complexity classes, Proceedings of 1980 IEEE Foundations of Computer Science Conference (to appear).","DOI":"10.1109\/SFCS.1980.17"}],"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_21.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,21]],"date-time":"2025-03-21T20:10:53Z","timestamp":1742587853000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-10291-4_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981]]},"ISBN":["9783540102915","9783540384359"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/3-540-10291-4_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1981]]}}}