{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,12]],"date-time":"2026-10-12T00:33:06Z","timestamp":1791765186599,"version":"4.3.4"},"reference-count":21,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2008,1]]},"abstract":"<jats:p>Let G be a connected graph, and let V and $V'$ be two n-element subsets of its vertex set $V(G)$. Imagine that we place a chip at each element of V and we want to move them into the positions of $V'$ (V and $V'$ may have common elements). A move is defined as shifting a chip from $v_1$ to $v_2$ ($v_1,v_2 \\in V(G)$) on a path formed by edges of G so that no intermediate vertices are occupied. We give upper and lower bounds on the number of moves that are necessary and analyze the computational complexity of this problem under various assumptions: labeled versus unlabeled chips, arbitrary graphs versus the case when the graph is the rectangular (infinite) planar grid, etc. We prove hardness and inapproximability results for several variants of the problem. We also give a linear time algorithm which performs an optimal (minimum) number of moves for the unlabeled version in a tree, and a constant-ratio approximation algorithm for the unlabeled version in a graph. The graph algorithm uses the tree algorithm as a subroutine.<\/jats:p>","DOI":"10.1137\/060652063","type":"journal-article","created":{"date-parts":[[2008,2,15]],"date-time":"2008-02-15T18:09:14Z","timestamp":1203098954000},"page":"124-138","source":"Crossref","is-referenced-by-count":39,"title":["Reconfigurations in Graphs and Grids"],"prefix":"10.1137","volume":"22","author":[{"given":"Gruia","family":"C\u0103linescu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adrian","family":"Dumitrescu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"J\u00e1nos","family":"Pach","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2008,2,15]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2005.06.005"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"P. Alimonti and V. Kann,\n                      Hardness of approximating problems on cubic graphs\n                      , in Proceedings of the 3rd Italian Conference on Algorithms and Complexity, Rome, Italy, Lecture Notes in Comput. Sci. 1203, Springer-Verlag, 1997, pp. 288\u2013298.","DOI":"10.1007\/3-540-62592-5_80"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.2307\/2589612"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1145\/273865.273870"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009259"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/s004530010009"},{"key":"R7","unstructured":"S. Bereg, A. Dumitrescu, and J. Pach,\n                      Sliding disks in the plane\n                      , Internat. J. Comput. Geom. & Appl., to appear."},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-006-1239-x"},{"key":"R9","doi-asserted-by":"crossref","unstructured":"A. Dumitrescu,\n                      Motion planning and reconfiguration for systems of multiple objects\n                      , in Mobile Robots: Perception & Navigation, S. Kolski, ed., Advanced Robotic Systems, 2007, pp. 523\u2013542.","DOI":"10.5772\/4788"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-005-0640-1"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1109\/TRA.2004.824936"},{"key":"R12","unstructured":"M. Garey and D. Johnson,\n                      Computers and Intractability: A Guide to the Theory of NP-Completeness\n                      , W. H. Freeman, San Francisco, 1979."},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793242618"},{"key":"R14","unstructured":"M. X. Goemans and D. P. Williamson,\n                      The primal-dual method for approximation algorithms and its application to network design problems\n                      , in Approximation Algorithms for NP-Hard Problems, D. S. Hochbaum, ed., PWS Publishing, Boston, 1995, pp. 144\u2013186."},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.2307\/2369492"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"D. Kornhauser, G. Miller, and P. Spirakis,\n                      Coordinating pebble motion on graphs, the diameter of permutation groups, and applications\n                      , in Proceedings of the 25th Symposium on Foundations of Computer Science (FOCS '84), IEEE Press, Piscataway, NJ, 1984, pp. 241\u2013250.","DOI":"10.1109\/SFCS.1984.715921"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"C. Papadimitriou, P. Raghavan, M. Sudan, and H. Tamaki,\n                      Motion planning on a graph\n                      , in Proceedings of the 35th Symposium on Foundations of Computer Science (FOCS '94), IEEE Press, Piscataway, NJ, 1994, pp. 511\u2013520.","DOI":"10.1109\/SFCS.1994.365740"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(08)80001-6"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.2307\/2369492"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(74)90098-7"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/060652063","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:01:11Z","timestamp":1787320871000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/060652063"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,1]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["10.1137\/060652063"],"URL":"https:\/\/doi.org\/10.1137\/060652063","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,1]]}}}