{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:48:22Z","timestamp":1759063702717},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540327554"},{"type":"electronic","value":"9783540327561"}],"license":[{"start":{"date-parts":[[2006,1,1]],"date-time":"2006-01-01T00:00:00Z","timestamp":1136073600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11682462_27","type":"book-chapter","created":{"date-parts":[[2006,2,17]],"date-time":"2006-02-17T06:50:30Z","timestamp":1140159030000},"page":"262-273","source":"Crossref","is-referenced-by-count":6,"title":["Reconfigurations in Graphs and Grids"],"prefix":"10.1007","author":[{"given":"Gruia","family":"Calinescu","sequence":"first","affiliation":[]},{"given":"Adrian","family":"Dumitrescu","sequence":"additional","affiliation":[]},{"given":"J\u00e1nos","family":"Pach","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"27_CR1","doi-asserted-by":"crossref","unstructured":"Abellanas, M., Bereg, S., Hurtado, F., Olaverri, A.G., Rappaport, D., Tejel, J.: Moving coins. Computational Geometry: Theory and Applications (to appear)","DOI":"10.1016\/j.comgeo.2005.06.005"},{"key":"27_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/3-540-62592-5_80","volume-title":"Algorithms and Complexity","author":"P. Alimonti","year":"1997","unstructured":"Alimonti, P., Kann, V.: Hardness of approximating problems on cubic graphs. In: Bongiovanni, G., Bovet, D.P., Di Battista, G. (eds.) CIAC 1997. LNCS, vol.\u00a01203, pp. 288\u2013298. Springer, Heidelberg (1997)"},{"key":"27_CR3","doi-asserted-by":"publisher","first-page":"793","DOI":"10.2307\/2589612","volume":"106","author":"A. Archer","year":"1999","unstructured":"Archer, A.: A modern treatment of the 15 puzzle. American Mathematical Monthly\u00a0106, 793\u2013799 (1999)","journal-title":"American Mathematical Monthly"},{"issue":"5","key":"27_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/290179.290180","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S.: Nearly linear time approximation schemes for Euclidean TSP and other geometric problems. J. of the ACM\u00a045(5), 1\u201330 (1998)","journal-title":"J. of the ACM"},{"key":"27_CR5","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/PL00009259","volume":"23","author":"V. Auletta","year":"1999","unstructured":"Auletta, V., Monti, A., Parente, M., Persiano, P.: A linear-time algorithm for the feasibility of pebble motion in trees. Algorithmica\u00a023, 223\u2013245 (1999)","journal-title":"Algorithmica"},{"key":"27_CR6","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/s004530010009","volume":"27","author":"R. Bar-Yehuda","year":"2000","unstructured":"Bar-Yehuda, R.: One for the Price of Two: A Unified approach for approximating covering problems. Algorithmica\u00a027, 131\u2013144 (2000)","journal-title":"Algorithmica"},{"key":"27_CR7","series-title":"Lecture Notes in Computer Science","volume-title":"Japan Conference on Discrete and Computational Geometry 2004","author":"S. Bereg","year":"2004","unstructured":"Bereg, S., Dumitrescu, A., Pach, J.: Sliding disks in the plane. In: Akiyama, J., Kano, M., Tan, X. (eds.) Japan Conference on Discrete and Computational Geometry 2004. LNCS, Springer, Heidelberg (2004) (to appear)"},{"key":"#cr-split#-27_CR8.1","unstructured":"Bereg, S., Dumitrescu, A.: The lifting model for reconfiguration, Discrete & Computational Geometry (accepted);"},{"key":"#cr-split#-27_CR8.2","unstructured":"A preliminary version in Proceedings of the 21st Annual Symposium on Computational Geometry (SOCG 2005), Pisa, Italy, pp. 55???62 (June 2005)"},{"key":"#cr-split#-27_CR9.1","unstructured":"Dumitrescu, A., Pach, J.: Pushing squares around, Graphs and Combinatorics (to appear);"},{"key":"#cr-split#-27_CR9.2","unstructured":"A preliminary version in Proceedings of the 20-th Annual Symposium on Computational Geometry (SOCG 2004), NY, June 2004, pp. 116???123 (2004)"},{"issue":"3","key":"27_CR10","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1109\/TRA.2004.824936","volume":"20","author":"A. Dumitrescu","year":"2004","unstructured":"Dumitrescu, A., Suzuki, I., Yamashita, M.: Motion planning for metamorphic systems: feasibility, decidability and distributed reconfiguration. IEEE Transactions on Robotics and Automation\u00a020(3), 409\u2013418 (2004)","journal-title":"IEEE Transactions on Robotics and Automation"},{"key":"27_CR11","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M. Garey","year":"1979","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)"},{"key":"27_CR12","unstructured":"Goemans, M.X., Williamson, D.P.: The primal-dual method for approximation algorithms and its application to network design problems. In: Hochbaum, D.S. (ed.) Approximation Algorithms for NP-Hard Problems. PWS Publishing Co. (1995)"},{"key":"27_CR13","doi-asserted-by":"publisher","first-page":"397","DOI":"10.2307\/2369492","volume":"2","author":"W.W. Johnson","year":"1879","unstructured":"Johnson, W.W.: Notes on the 15 puzzle. I. American Journal of Mathematics\u00a02, 397\u2013399 (1879)","journal-title":"American Journal of Mathematics"},{"key":"27_CR14","doi-asserted-by":"crossref","unstructured":"Kornhauser, D., Miller, G., Spirakis, P.: Coordinating pebble motion on graphs, the diameter of permutation groups, and applications. In: Proceedings of the 25th Symposium on Foundations of Computer Science (FOCS 1984), pp. 241\u2013250 (1984)","DOI":"10.1109\/SFCS.1984.715921"},{"key":"27_CR15","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C., Raghavan, P., Sudan, M., Tamaki, H.: Motion planning on a graph. In: Proceedings of the 35-th Symposium on Foundations of Computer Science (FOCS 1994), pp. 511\u2013520 (1994)","DOI":"10.1109\/SFCS.1994.365740"},{"key":"27_CR16","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"C. Papadimitriou","year":"1991","unstructured":"Papadimitriou, C., Yannakakis, M.: Optimization, approximation, and complexity classes. Journal of Computer and System Sciences\u00a043, 425\u2013440 (1991)","journal-title":"Journal of Computer and System Sciences"},{"key":"27_CR17","doi-asserted-by":"publisher","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 \u00d7 N)- extension of the 15-puzzle is intractable. Journal of Symbolic Computation\u00a010, 111\u2013137 (1990)","journal-title":"Journal of Symbolic Computation"},{"key":"27_CR18","doi-asserted-by":"publisher","first-page":"399","DOI":"10.2307\/2369236","volume":"2","author":"W.E. Story","year":"1879","unstructured":"Story, W.E.: Notes on the 15 puzzle. II. American Journal of Mathematics\u00a02, 399\u2013404 (1879)","journal-title":"American Journal of Mathematics"},{"key":"27_CR19","doi-asserted-by":"publisher","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. Journal of Combinatorial Theory, Series B\u00a016, 86\u201396 (1974)","journal-title":"Journal of Combinatorial Theory, Series B"}],"container-title":["Lecture Notes in Computer Science","LATIN 2006: Theoretical Informatics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11682462_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,12]],"date-time":"2019-03-12T03:38:45Z","timestamp":1552361925000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11682462_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540327554","9783540327561"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/11682462_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2006]]}}}