{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:50:53Z","timestamp":1725490253266},"publisher-location":"Berlin, Heidelberg","reference-count":9,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424963"},{"type":"electronic","value":"9783540446835"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44683-4_51","type":"book-chapter","created":{"date-parts":[[2007,8,29]],"date-time":"2007-08-29T01:32:38Z","timestamp":1188351158000},"page":"585-597","source":"Crossref","is-referenced-by-count":3,"title":["The Complexity of Computing the Number of Self-Avoiding Walks in Two-Dimensional Grid Graphs and in Hypercube Graphs"],"prefix":"10.1007","author":[{"given":"Mitsunori","family":"Ogihara","sequence":"first","affiliation":[]},{"given":"Seinosuke","family":"Toda","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,9,5]]},"reference":[{"key":"51_CR1","doi-asserted-by":"publisher","first-page":"5284","DOI":"10.1103\/PhysRevLett.77.5284","volume":"77","author":"A. R. Conway","year":"1996","unstructured":"A. R. Conway and A. J. Guttmann. Square lattice self-avoiding walks and corrections-to-scaling. Physical Review Letters, 77:5284\u20135287, 1996.","journal-title":"Physical Review Letters"},{"key":"51_CR2","doi-asserted-by":"crossref","unstructured":"M. Chrobak and T. H. Payne. A linear time algorithm for drawing a planar graph on a grid. Information Processing Letters, pages 241\u2013246, 1995.","DOI":"10.1016\/0020-0190(95)00020-D"},{"issue":"4","key":"51_CR3","doi-asserted-by":"publisher","first-page":"704","DOI":"10.1137\/0205049","volume":"5","author":"M. Garey","year":"1976","unstructured":"M. Garey, D. Johnson, and E. Tarjan. The planar Hamiltonian circuit problem is NP-complete. SIAM Journal on Computing, 5(4):704\u2013714, 1976.","journal-title":"SIAM Journal on Computing"},{"key":"51_CR4","unstructured":"N. Madras and G. Slade. The Self-Avoiding Walk. Birkh\u00e1user, Boston, MA, 1993."},{"key":"51_CR5","unstructured":"C. Papadimitriou. Computational Complexity. Addison-Wesley, 1994."},{"key":"51_CR6","doi-asserted-by":"crossref","unstructured":"T. Schaefer. The complexity of satisfiability problem. In Proceedings of 10th Symposium on Theory of Computing, pages 216\u2013226. ACM Press, 1978.","DOI":"10.1145\/800133.804350"},{"key":"51_CR7","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/0304-3975(79)90044-6","volume":"8","author":"L. Valiant","year":"1979","unstructured":"L. Valiant. The complexity of computing the permanent. Theoretical Computer Science, 8:189\u2013201, 1979.","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"51_CR8","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L. Valiant","year":"1979","unstructured":"L. Valiant. The complexity of enumeration and reliability problems. SIAM Journal on Computing, 8(3):410\u2013421, 1979.","journal-title":"SIAM Journal on Computing"},{"key":"51_CR9","doi-asserted-by":"crossref","unstructured":"D. Welsh. Complexity: Knots, Colourings and Counting. Cambridge University Press, 1993.","DOI":"10.1017\/CBO9780511752506"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2001"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44683-4_51","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,23]],"date-time":"2019-02-23T06:15:38Z","timestamp":1550902538000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44683-4_51"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424963","9783540446835"],"references-count":9,"URL":"https:\/\/doi.org\/10.1007\/3-540-44683-4_51","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}