{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T21:10:26Z","timestamp":1725484226048},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540438649"},{"type":"electronic","value":"9783540454656"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2002]]},"DOI":"10.1007\/3-540-45465-9_24","type":"book-chapter","created":{"date-parts":[[2007,5,27]],"date-time":"2007-05-27T01:12:57Z","timestamp":1180228377000},"page":"269-280","source":"Crossref","is-referenced-by-count":3,"title":["Paths Problems in Symmetric Logarithmic Space"],"prefix":"10.1007","author":[{"given":"Andreas","family":"Jakoby","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maciej","family":"Liskiewicz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2002,6,25]]},"reference":[{"key":"24_CR1","doi-asserted-by":"crossref","unstructured":"R. Aleliunas, R. Karp, R. Lipton, L. Lovasz, C. Rackoff, Random Walks, Universal Sequences and the Complexity of Maze Problems, FOCS, 1979, 218\u2013223.","DOI":"10.1109\/SFCS.1979.34"},{"key":"24_CR2","doi-asserted-by":"crossref","unstructured":"E. Allender, M. Mahajan, The Complexity of Planarity Testing, STACS, 2000, 87\u201398.","DOI":"10.1007\/3-540-46541-3_7"},{"key":"24_CR3","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1006\/inco.1995.1122","volume":"121","author":"Y. Ben-Asher","year":"1995","unstructured":"Y. Ben-Asher, K.-J. Lange, D. Peleg, and A. Schuster, The Complexity of Reconfiguring Network Models, Inf. & Comp. 121, 1995, 41\u201358.","journal-title":"Inf. & Comp."},{"key":"24_CR4","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1137\/0221006","volume":"21","author":"B.-O. M","year":"1992","unstructured":"M. Ben-Or, R. Cleve Computing Algebraic Formulas Using a Constant Number of Registers, SIAM J. Comput. 21, 1992, 54\u201358.","journal-title":"SIAM J. Comput."},{"key":"24_CR5","doi-asserted-by":"crossref","unstructured":"H. Bodlaender, B. de Fluiter, Parallel Algorithms for Series Parallel Graphs, ESA, 1996, 277\u2013289.","DOI":"10.1007\/3-540-61680-2_62"},{"key":"24_CR6","doi-asserted-by":"publisher","first-page":"755","DOI":"10.1137\/0221046","volume":"21","author":"S. Buss","year":"1992","unstructured":"S. Buss, S. Cook, A. Gupta, V. Ramachandran, An Optimal Parallel Algorithm for Formula Evaluation, SIAM J. Comput. 21, 1992, 755\u2013780.","journal-title":"SIAM J. Comput."},{"key":"24_CR7","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1051\/ita:2001119","volume":"35","author":"C. A","year":"2001","unstructured":"A. Chiu, G. Davida, B. Litow, Division in logspace-uniform NC1, Theoretical Informatics and Applications, 35, 2001, 259\u2013275.","journal-title":"Theoretical Informatics and Applications"},{"key":"24_CR8","first-page":"99","volume":"XXVIII","author":"S. Cook","year":"1981","unstructured":"S. Cook, Towards a complexity theory of synchronous parallel computation, L\u2019Enseignement Mathematique, XXVIII, 1981, 99\u2013124.","journal-title":"L\u2019Enseignement Mathematique"},{"key":"24_CR9","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1016\/0022-247X(65)90125-3","volume":"10","author":"R. Duffin","year":"1965","unstructured":"R. Duffin, Topology of Series-Parallel Networks, J. Math. Analysis Appl. 10, 1965, 303\u2013318.","journal-title":"J. Math. Analysis Appl."},{"key":"24_CR10","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0890-5401(92)90041-D","volume":"98","author":"D. Eppstein","year":"1992","unstructured":"D. Eppstein, Parallel Recognition of Series-Parallel Graphs, Inf. & Comp. 98, 1992, 41\u201355.","journal-title":"Inf. & Comp."},{"key":"24_CR11","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"F. S","year":"1980","unstructured":"S. Fortune, J. Hopcroft and J. Wyllie, The directed subgraph homomorphism problem, Theoretical Computer Science 10, 1980, 111\u2013121.","journal-title":"Theoretical Computer Science"},{"key":"24_CR12","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/0890-5401(87)90061-7","volume":"75","author":"X. He","year":"1987","unstructured":"X. He, Y. Yesha, Parallel Recognition and Decomposition of Two Terminal Series Parallel Graphs, Inf. & Comp. 75, 1987, 15\u201338.","journal-title":"Inf. & Comp."},{"key":"24_CR13","unstructured":"B. Jenner, K.-J. Lange, P. McKenzie, Tree Isomorphism and Some Other Complete Problems for Deterministic Logspace, publication #1059, DIRO, Universit\u00e9 de Montr\u00e9al, 1997."},{"key":"24_CR14","doi-asserted-by":"crossref","unstructured":"A. Jakoby, M. Li\u015bkiewicz, R. Reischuk, Space Efficient Algorithms for Series-Parallel Graphs STACS, 2001, 339\u2013352. See also ECCC Report TR02-021, 2002.","DOI":"10.1007\/3-540-44693-1_30"},{"key":"24_CR15","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","volume":"5","author":"R. Karp","year":"1975","unstructured":"R. Karp, On the complexity of the combinatorial problems, Networks 5, 1975, 45\u201348.","journal-title":"Networks"},{"key":"24_CR16","doi-asserted-by":"crossref","unstructured":"A. K\u00e9zdy and P. McGuinness, Sequential and Parallel Algorithms to Find a K5 Minor, SODA, 1992, 345\u2013356.","DOI":"10.21236\/ADA232901"},{"key":"24_CR17","doi-asserted-by":"crossref","unstructured":"M. Li\u015bkiewicz, M. Ogihara, and S. Toda, The Complexity of Counting Self-Avoiding Walks in Two-Dimensional Grid Graphs and in Hypercube Graphs, ECCC Report TR01-061, 2001.","DOI":"10.1016\/S0304-3975(02)00886-1"},{"key":"24_CR18","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0304-3975(82)90058-5","volume":"19","author":"H. R. Lewis","year":"1982","unstructured":"H. R. Lewis and C. H. Papadimitriou, Symmetric space-bounded computations, Theoretical Computer Science 19, 1982, 161\u2013187.","journal-title":"Theoretical Computer Science"},{"key":"24_CR19","doi-asserted-by":"crossref","unstructured":"N. Nisan and A. Ta-Shma, Symmetric logspace is closed under complement, FoCS, 1995, 140\u2013146.","DOI":"10.1145\/225058.225101"},{"issue":"2","key":"24_CR20","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1145\/62.322436","volume":"31","author":"J. Reif","year":"1984","unstructured":"J. Reif, Symmetric Complementation, Journal of the ACM, vol. 31(2), 1984, 401\u2013421.","journal-title":"Journal of the ACM"},{"key":"24_CR21","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"B 63","author":"N. Robertson","year":"1995","unstructured":"N. Robertson, P. D. Seymour, Graph Minors XIII. The Disjoint Paths Problems, J. of Combinatorial Theory, Series B 63, 1995, 65\u2013110.","journal-title":"J. of Combinatorial Theory, Series"},{"key":"24_CR22","unstructured":"N. Robertson, P. D. Seymour, R. Thomas, Non-Planar Extensions Of Planar Graphs, http:\/\/www.math.gatech.edu\/~thomas\/ext.ps"},{"key":"24_CR23","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0012-365X(80)90158-2","volume":"29","author":"P. D. Seymour","year":"1980","unstructured":"P. D. Seymour, Disjoint paths in Graphs, Discrete Math. 29, 1980, 293\u2013309.","journal-title":"Discrete Math."},{"key":"24_CR24","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1145\/322203.322207","volume":"27","author":"Y. Shiloach","year":"1980","unstructured":"Y Shiloach, A Polynomial Solution to the Undirected Two Paths Problem, J. of the ACM, Vol. 27, 1980, 445\u2013456.","journal-title":"J. of the ACM"},{"key":"24_CR25","doi-asserted-by":"crossref","unstructured":"R. Thomas, Graph Planarity and Related Topics, Graph Drawing, 1999, 137\u2013144.","DOI":"10.1007\/3-540-46648-7_14"},{"key":"24_CR26","doi-asserted-by":"crossref","first-page":"371","DOI":"10.1016\/S0195-6698(80)80039-4","volume":"1","author":"C. Thomassen","year":"1980","unstructured":"C. Thomassen, 2-linked Graphs, Europ. J. Combinatorics 1, 1980, 371\u2013378.","journal-title":"Europ. J. Combinatorics"},{"issue":"4","key":"24_CR27","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0020-0190(90)90071-5","volume":"36","author":"W. G","year":"1990","unstructured":"G. Woeginger, A simple solution to the two paths problem in planar graphs, Inform. Process. Lett. 36, 1990, No. 4, 191\u2013192.","journal-title":"Inform. Process. Lett."},{"key":"24_CR28","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1137\/0211023","volume":"11","author":"V. J","year":"1982","unstructured":"J. Valdes, R. Tarjan, E. Lawlers The Recognition of Series Parallel Digraphs, SIAM J. Comput. 11, 1982, 298\u2013313.","journal-title":"SIAM J. Comput."}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45465-9_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T11:06:03Z","timestamp":1556449563000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-45465-9_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002]]},"ISBN":["9783540438649","9783540454656"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/3-540-45465-9_24","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2002]]}}}