{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:29:27Z","timestamp":1725488967629},"publisher-location":"Berlin, Heidelberg","reference-count":11,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540744559"},{"type":"electronic","value":"9783540744566"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-74456-6_65","type":"book-chapter","created":{"date-parts":[[2007,8,14]],"date-time":"2007-08-14T03:29:48Z","timestamp":1187062188000},"page":"738-749","source":"Crossref","is-referenced-by-count":4,"title":["Finding Paths Between Graph Colourings: PSPACE-Completeness and Superpolynomial Distances"],"prefix":"10.1007","author":[{"given":"Paul","family":"Bonsma","sequence":"first","affiliation":[]},{"given":"Luis","family":"Cereceda","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"65_CR1","volume-title":"Graph Theory","author":"R. Diestel","year":"2005","unstructured":"Diestel, R.: Graph Theory, 3rd edn. Springer, Heidelberg (2005)","edition":"3"},{"key":"65_CR2","volume-title":"Computational Complexity","author":"C.H. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"65_CR3","unstructured":"Cereceda, L., van den Heuvel, J., Johnson, M.: Connectedness of the graph of vertex-colourings. CDAM Research Report LSE-CDAM-2005 -11(accepted for publication in Discrete Math.) (2005), available from \n                    \n                      http:\/\/www.cdam.lse.ac.uk\/Reports\/reports2005.html"},{"key":"65_CR4","unstructured":"Cereceda, L., van den Heuvel, J., Johnson, M.: Mixing 3-colourings in bipartite graphs. CDAM Research Report LSE-CDAM-2007-06 (submitted, 2007), available from \n                    \n                      http:\/\/www.cdam.lse.ac.uk\/Reports\/reports2007.html"},{"key":"65_CR5","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-0348-8005-3","volume-title":"Counting, Sampling and Integrating : Algorithms and Complexity","author":"M. Jerrum","year":"2003","unstructured":"Jerrum, M.: Counting, Sampling and Integrating : Algorithms and Complexity. Birkh\u00e4user Verlag, Basel (2003)"},{"key":"65_CR6","unstructured":"Cereceda, L., van den Heuvel, J., Johnson, M.: Finding paths between 3-colourings (in preparation)"},{"key":"65_CR7","unstructured":"Billingham, J., Leese, R., Rajaniemi, H., et al.: Frequency reassignment in cellular phone networks, Smith Institute Study Group Report (2005), available from \n                    \n                      http:\/\/www.smithinst.ac.uk\/Projects\/ESGI53\/ESGI53-Motorola\/index_html"},{"key":"65_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1007\/11786986_31","volume-title":"Automata, Languages and Programming","author":"P. Gopalan","year":"2006","unstructured":"Gopalan, P., Kolaitis, P.G., Maneva, E.N., Papadimitriou, C.H.: The connectivity of Boolean satisfiability: computational and structural dichotomies. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04051, pp. 346\u2013357. Springer, Heidelberg (2006), available from \n                    \n                      http:\/\/arxiv.org\/abs\/cs.CC\/0609072"},{"key":"65_CR9","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1016\/j.tcs.2005.05.008","volume":"343","author":"R.A. Hearn","year":"2005","unstructured":"Hearn, R.A., Demaine, E.D.: PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation. Theoret. Comput. Sci.\u00a0343, 72\u201396 (2005)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"65_CR10","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. Comput. Syst. Sci.\u00a04(2), 177\u2013192 (1970)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"65_CR11","doi-asserted-by":"publisher","first-page":"450","DOI":"10.1002\/rsa.20129","volume":"29","author":"M. Dyer","year":"2006","unstructured":"Dyer, M., Flaxman, A., Frieze, A., Vigoda, E.: Randomly colouring sparse random graphs with fewer colours than the maximum degree. Random Struct. Algor.\u00a029(4), 450\u2013465 (2006)","journal-title":"Random Struct. Algor."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74456-6_65","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T21:12:34Z","timestamp":1558473154000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74456-6_65"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540744559","9783540744566"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74456-6_65","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}