{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,2]],"date-time":"2025-11-02T16:28:31Z","timestamp":1762100911863},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,2,25]],"date-time":"2009-02-25T00:00:00Z","timestamp":1235520000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2010,11]]},"DOI":"10.1007\/s00453-009-9290-7","type":"journal-article","created":{"date-parts":[[2009,2,24]],"date-time":"2009-02-24T20:58:56Z","timestamp":1235509136000},"page":"610-636","source":"Crossref","is-referenced-by-count":24,"title":["Multi-Color Pebble Motion on Graphs"],"prefix":"10.1007","volume":"58","author":[{"given":"Gilad","family":"Goraly","sequence":"first","affiliation":[]},{"given":"Refael","family":"Hassin","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2009,2,25]]},"reference":[{"key":"9290_CR1","doi-asserted-by":"crossref","first-page":"793","DOI":"10.1080\/00029890.1999.12005124","volume":"106","author":"A.F. Archer","year":"1999","unstructured":"Archer, A.F.: Modern treatment of the 15 puzzle. Am. Math. Mon. 106, 793\u2013799 (1999)","journal-title":"Am. Math. Mon."},{"key":"9290_CR2","doi-asserted-by":"crossref","first-page":"42","DOI":"10.1006\/inco.2000.3005","volume":"165","author":"V. Auletta","year":"2001","unstructured":"Auletta, V., Persiano, P.: Optimal pebble motion on a tree. Inf. Comput. 165, 42\u201368 (2001)","journal-title":"Inf. Comput."},{"key":"9290_CR3","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1007\/PL00009259","volume":"23","author":"V. Auletta","year":"1999","unstructured":"Auletta, V., Monti, A., Parente, D., Persiano, G.: A linear time algorithm for the feasibility of pebble motion on trees. Algorithmica 23, 223\u2013245 (1999)","journal-title":"Algorithmica"},{"key":"9290_CR4","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1287\/opre.21.2.577","volume":"21","author":"N. Christofides","year":"1973","unstructured":"Christofides, N., Colloff, I.: The rearrangement of items in a warehouse. Oper. Res. 21, 577\u2013589 (1973)","journal-title":"Oper. Res."},{"key":"9290_CR5","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1137\/060652063","volume":"22","author":"G. C\u0103linescu","year":"2008","unstructured":"C\u0103linescu, G., Dumitrescu, A., Pach, J.: Reconfigurations in graphs and grids. SIAM J. Discrete Math. 22, 124\u2013138 (2008)","journal-title":"SIAM J. Discrete Math."},{"key":"9290_CR6","doi-asserted-by":"crossref","unstructured":"Dumitrescu, A., Pach, J.: Pushing squares around. In: Graphs and Combinatorics, pp. 37\u201350 (2006)","DOI":"10.1007\/s00373-005-0640-1"},{"key":"9290_CR7","unstructured":"Goldreich, O.: Shortest move-sequence in the generalized 15-Puzzle is NP-hard. Technical Report no.\u00a0792, Computer Science Department, Technion (1993)"},{"key":"9290_CR8","unstructured":"Hayes, R.: The Sam Loyd 15-puzzle. Technical Report no. TCD-CS-2001-24, Computer Science Department, The University of Dublin, Trinity College (2001)"},{"key":"9290_CR9","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1006\/jcph.1997.5809","volume":"137","author":"D.J. Jacobs","year":"1997","unstructured":"Jacobs, D.J., Hendrickson, B.: An algorithm for two-dimensional rigidity percolation: the pebble game. J. Comput. Phys. 137, 346\u2013365 (1997)","journal-title":"J. Comput. Phys."},{"key":"9290_CR10","doi-asserted-by":"crossref","first-page":"150","DOI":"10.1002\/prot.1081","volume":"44","author":"D.J. Jacobs","year":"2001","unstructured":"Jacobs, D.J., Rader, A.J., Kuhn, L.A., Thorpe, M.F.: Protein flexibility predictions using graph theory. Proteins Struct. Funct. Genet. 44, 150\u2013165 (2001)","journal-title":"Proteins Struct. Funct. Genet."},{"key":"9290_CR11","doi-asserted-by":"crossref","unstructured":"Kornhauser, D., Miller, G., Spirakis, P.: Coordinating pebble motion on graph, the diameter of permutation groups, and applications. In: Proceedings of the 25-th Symposium on the Foundations of Computer Science (FOCS), pp. 241\u2013250 (1984)","DOI":"10.1109\/SFCS.1984.715921"},{"key":"9290_CR12","doi-asserted-by":"crossref","unstructured":"Milans, K., Clark, B.: The complexity of graph pebbling. SIDMA 20(3) (2006) (archived in 2005 at http:\/\/arxiv.org\/abs\/math\/0503698 )","DOI":"10.1137\/050636218"},{"key":"9290_CR13","volume-title":"Mathematical Puzzles of Sam Loyd","author":"S. Loyd","year":"1959","unstructured":"Loyd, S.: Mathematical Puzzles of Sam Loyd. Dover, New York (1959)"},{"key":"9290_CR14","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/0020-0190(95)00134-X","volume":"56","author":"I. Parberry","year":"1995","unstructured":"Parberry, I.: A real-time algorithm for the (n 2\u22121)-puzzle. Inf. Process. Lett. 56, 23\u201328 (1995)","journal-title":"Inf. Process. Lett."},{"key":"9290_CR15","doi-asserted-by":"crossref","unstructured":"Papadimitriou, D., Raghavan, P., Sudan, M., Tamaki, H.: Motion planning on a graph. In: Proceedings of the 35-th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 511\u2013520 (1994)","DOI":"10.1109\/SFCS.1994.365740"},{"key":"9290_CR16","unstructured":"Stagemann, R.: Rob\u2019s puzzle page. http:\/\/home.comcast.net\/~stegmann\/sliding.htm"},{"key":"9290_CR17","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/S0747-7171(08)80001-6","volume":"10","author":"D. Ratner","year":"1990","unstructured":"Ratner, D., Warmuth, M.: Finding a shortest solution for the (N\u00d7N)-extension of the 15 puzzle is NP-hard. J. Symb. Comput. 10, 111\u2013137 (1990)","journal-title":"J. Symb. Comput."},{"key":"9290_CR18","unstructured":"Reinefeld, A.: Complete solution of the eight-puzzle and the benefit of node ordering in IDA. In: Proceeding of the International Joint Conference on Artificial Intelligence, pp. 248\u2013253 (1993)"},{"key":"9290_CR19","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0095-8956(74)90098-7","volume":"16","author":"R.M. Wilson","year":"1974","unstructured":"Wilson, R.M.: Graph puzzles, homotopy, and the alternating group. J. Comb. Theory Ser. B 16, 86\u201394 (1974)","journal-title":"J. Comb. Theory Ser. B"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9290-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-009-9290-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-009-9290-7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T13:45:03Z","timestamp":1559137503000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-009-9290-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2,25]]},"references-count":19,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,11]]}},"alternative-id":["9290"],"URL":"https:\/\/doi.org\/10.1007\/s00453-009-9290-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,2,25]]}}}