{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T14:09:02Z","timestamp":1778594942921,"version":"3.51.4"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"9","license":[{"start":{"date-parts":[[2017,10,20]],"date-time":"2017-10-20T00:00:00Z","timestamp":1508457600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["280152"],"award-info":[{"award-number":["280152"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["280152"],"award-info":[{"award-number":["280152"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["280152"],"award-info":[{"award-number":["280152"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2018,9]]},"DOI":"10.1007\/s00453-017-0387-0","type":"journal-article","created":{"date-parts":[[2017,10,20]],"date-time":"2017-10-20T10:08:32Z","timestamp":1508494112000},"page":"2656-2682","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":26,"title":["Complexity of Token Swapping and Its Variants"],"prefix":"10.1007","volume":"80","author":[{"given":"\u00c9douard","family":"Bonnet","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tillmann","family":"Miltzow","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7696-3848","authenticated-orcid":false,"given":"Pawe\u0142","family":"Rz\u0105\u017cewski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,10,20]]},"reference":[{"key":"387_CR1","volume-title":"Winning Ways, for Your Mathematical Plays: Games in Particular","author":"ER Berlekamp","year":"1982","unstructured":"Berlekamp, E.R., Conway, J.H., Guy, R.K.: Winning Ways, for Your Mathematical Plays: Games in Particular, vol. 2. Academic Press, New York (1982)"},{"key":"387_CR2","doi-asserted-by":"crossref","unstructured":"Bodlaender, H.L., Nederlof, J.: Subexponential time algorithms for finding small tree and path decompositions. In: ESA 2015 Proceedings, pp. 179\u2013190. Springer (2015)","DOI":"10.1007\/978-3-662-48350-3_16"},{"key":"387_CR3","unstructured":"Bonnet, \u00c9, Miltzow, T., Rzazewski, P.: Complexity of token swapping and its variants. In: Vollmer, H., Vall\u00e9e, B. (eds.) 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), vol.\u00a066 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 16:1\u201316:14, Dagstuhl, Germany (2017). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik"},{"issue":"1","key":"387_CR4","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1016\/j.comgeo.2008.04.001","volume":"42","author":"P Bose","year":"2009","unstructured":"Bose, P., Hurtado, F.: Flips in planar graphs. Comput. Geometry 42(1), 60\u201380 (2009)","journal-title":"Comput. Geometry"},{"key":"387_CR5","doi-asserted-by":"crossref","unstructured":"Calinescu, G., Dumitrescu, A., Pach, J.: Reconfigurations in graphs and grids. In: LATIN 2006 Proceedings, pp. 262\u2013273. Springer (2006)","DOI":"10.1007\/11682462_27"},{"issue":"232","key":"387_CR6","first-page":"527","volume":"34","author":"A Cayley","year":"1849","unstructured":"Cayley, A.: LXXVII. Note on the theory of permutations. Philos. Mag. Ser. 3 34(232), 527\u2013529 (1849)","journal-title":"Philos. Mag. Ser. 3"},{"issue":"1","key":"387_CR7","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1016\/0166-218X(84)90075-1","volume":"8","author":"CJ Colbourn","year":"1984","unstructured":"Colbourn, C.J.: The complexity of completing partial latin squares. Discrete Appl. Math. 8(1), 25\u201330 (1984)","journal-title":"Discrete Appl. Math."},{"key":"387_CR8","doi-asserted-by":"crossref","unstructured":"De\u00a0Berg, M., Van\u00a0Kreveld, M., Overmars, M., Schwarzkopf, O.C.: Computational geometry. In: Computational Geometry, pp. 1\u201317. Springer (2000)","DOI":"10.1007\/978-3-662-04245-8_1"},{"key":"387_CR9","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/j.tcs.2015.07.037","volume":"600","author":"ED Demaine","year":"2015","unstructured":"Demaine, E.D., Demaine, M.L., Fox-Epstein, E., Hoang, D.A., Ito, T., Ono, H., Otachi, Y., Uehara, R., Yamada, T.: Linear-time algorithm for sliding tokens on trees. Theor. Comput. Sci. 600, 132\u2013142 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"387_CR10","doi-asserted-by":"crossref","unstructured":"Erd\u0151s, P., Szekeres, G.: Classic papers in combinatorics. In: Chapter A Combinatorial Problem in Geometry, pp. 49\u201356. Birkh\u00e4user Boston, Boston, MA (1987)","DOI":"10.1007\/978-0-8176-4842-8_3"},{"issue":"3","key":"387_CR11","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/s00373-011-1055-9","volume":"28","author":"R Fabila-Monroy","year":"2012","unstructured":"Fabila-Monroy, R., Flores-Pe\u00f1aloza, D., Huemer, C., Hurtado, F., Urrutia, J., Wood, D.R.: Token graphs. Graphs Combin. 28(3), 365\u2013380 (2012)","journal-title":"Graphs Combin."},{"key":"387_CR12","doi-asserted-by":"crossref","unstructured":"Farnoud, F., Chen, C.Y., Milenkovic, O., Kashyap, N.: A graphical model for computing the minimum cost transposition distance. In: Information Theory Workshop (ITW), 2010 IEEE, pp. 1\u20135 (2010)","DOI":"10.1109\/CIG.2010.5592890"},{"issue":"1","key":"387_CR13","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1109\/TIT.2011.2171532","volume":"58","author":"F Farnoud","year":"2012","unstructured":"Farnoud, F., Milenkovic, O.: Sorting of permutations by cost-constrained transpositions. IEEE Trans. Inf. Theory 58(1), 3\u201323 (2012)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"387_CR14","first-page":"237","volume-title":"Algorithms and Computation, volume 9472 of Lecture Notes in Computer Science","author":"E Fox-Epstein","year":"2015","unstructured":"Fox-Epstein, E., Hoang, D.A., Otachi, Y., Uehara, R.: Sliding token on bipartite permutation graphs. In: Elbassioni, K., Makino, K. (eds.) Algorithms and Computation, volume 9472 of Lecture Notes in Computer Science, pp. 237\u2013247. Springer, Berlin (2015)"},{"key":"387_CR15","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"TF Gonzalez","year":"1985","unstructured":"Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance. Theor. Comput. Sci. 38, 293\u2013306 (1985)","journal-title":"Theor. Comput. Sci."},{"key":"387_CR16","doi-asserted-by":"crossref","unstructured":"Graf, D.: How to sort by walking on a tree. In: ESA 2015 Proceeding, pp. 643\u2013655. Springer (2015)","DOI":"10.1007\/978-3-662-48350-3_54"},{"key":"387_CR17","doi-asserted-by":"crossref","unstructured":"Grohe, M., Kreutzer, S., Siebertz, S.: Deciding first-order properties of nowhere dense graphs. In: STOC 2014 Proceedings, pp. 89\u201398. ACM (2014)","DOI":"10.1145\/2591796.2591851"},{"key":"387_CR18","unstructured":"Gu\u015bpiel, G.: Complexity of finding perfect bipartite matchings minimizing the number of intersecting edges. CoRR, arXiv:1709.06805 (2017)"},{"issue":"5","key":"387_CR19","doi-asserted-by":"crossref","first-page":"775","DOI":"10.1089\/106652703322539097","volume":"10","author":"LS Heath","year":"2003","unstructured":"Heath, L.S., Vergara, J.P.C.: Sorting by short swaps. J. Comput. Biol. 10(5), 775\u2013789 (2003)","journal-title":"J. Comput. Biol."},{"issue":"4","key":"387_CR20","doi-asserted-by":"crossref","first-page":"713","DOI":"10.1137\/0210054","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer, I.: The NP-completeness of some edge-partition problems. SIAM J. Comput. 10(4), 713\u2013717 (1981)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"387_CR21","doi-asserted-by":"crossref","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-sat. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"387_CR22","doi-asserted-by":"crossref","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"387_CR23","doi-asserted-by":"crossref","first-page":"574","DOI":"10.1137\/0208046","volume":"8","author":"T Kasai","year":"1979","unstructured":"Kasai, T., Adachi, A., Iwata, S.: Classes of pebble games and complete problems. SIAM J. Comput. 8(4), 574\u2013586 (1979)","journal-title":"SIAM J. Comput."},{"key":"387_CR24","unstructured":"Knuth, D.E.: The Art of Computer Programming, volume 3\/Sorting and Searching. Addison-Wesley (1982). ISBN 0-201-03803-X"},{"key":"387_CR25","first-page":"41","volume":"105","author":"D Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the exponential time hypothesis. Bull. EATCS 105, 41\u201372 (2011)","journal-title":"Bull. EATCS"},{"issue":"1","key":"387_CR26","doi-asserted-by":"crossref","first-page":"85","DOI":"10.4086\/toc.2010.v006a005","volume":"6","author":"D Marx","year":"2010","unstructured":"Marx, D.: Can you beat treewidth? Theory Comput. 6(1), 85\u2013112 (2010)","journal-title":"Theory Comput."},{"key":"387_CR27","doi-asserted-by":"crossref","unstructured":"Marx, D., Pilipczuk, M.: Optimal parameterized algorithms for planar facility location problems using voronoi diagrams. CoRR, abs\/1504.05476 (2015)","DOI":"10.1007\/978-3-662-48350-3_72"},{"key":"387_CR28","unstructured":"Miltzow, T., Narins, L., Okamoto, Y., Rote, G., Thomas, A., Uno, T.: Approximation and hardness of token swapping. In: Sankowski, P., Zaroliagis, C. (eds.) 24th Annual European Symposium on Algorithms (ESA 2016)"},{"key":"387_CR29","volume-title":"Sparsity\u2014Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics","author":"J Ne\u0161et\u0159il","year":"2012","unstructured":"Ne\u0161et\u0159il, J., Ossona de Mendez, P.: Sparsity\u2014Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, Berlin (2012)"},{"issue":"1","key":"387_CR30","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/S0012-365X(98)00377-X","volume":"204","author":"I Pak","year":"1999","unstructured":"Pak, I.: Reduced decompositions of permutations in terms of star transpositions, generalized Catalan numbers and k-ARY trees. Discrete Math. 204(1), 329\u2013335 (1999)","journal-title":"Discrete Math."},{"key":"387_CR31","doi-asserted-by":"crossref","unstructured":"Parsons, T.D.: Pursuit-evasion in a graph. In: Alavi, Y., Lick, D.R. (eds.) Theory and Applications of Graphs. Lecture Notes in Mathematics, pp. 426\u2013441. Springer (1976)","DOI":"10.1007\/BFb0070400"},{"issue":"4","key":"387_CR32","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1016\/0020-0190(79)90023-1","volume":"8","author":"J Plesn\u00edk","year":"1979","unstructured":"Plesn\u00edk, J.: The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two. Inf. Process. Lett. 8(4), 199\u2013201 (1979)","journal-title":"Inf. Process. Lett."},{"issue":"30","key":"387_CR33","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1112\/plms\/s2-30.1.264","volume":"3","author":"FP Ramsey","year":"1930","unstructured":"Ramsey, F.P.: On a problem in formal logic. Proc. Lond. Math. Soc. 3(30), 264\u2013286 (1930)","journal-title":"Proc. Lond. Math. Soc."},{"issue":"2","key":"387_CR34","doi-asserted-by":"crossref","first-page":"177","DOI":"10.1016\/S0022-0000(70)80006-X","volume":"4","author":"WJ Savitch","year":"1970","unstructured":"Savitch, W.J.: Relationships between nondeterministic and deterministic tape complexities. J. Comput. Syst. Sci. 4(2), 177\u2013192 (1970)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"387_CR35","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1016\/0095-8956(74)90098-7","volume":"16","author":"RM Wilson","year":"1974","unstructured":"Wilson, R.M.: Graph puzzles, homotopy, and the alternating group. J. Combin. Theory Ser. B 16(1), 86\u201396 (1974)","journal-title":"J. Combin. Theory Ser. B"},{"key":"387_CR36","doi-asserted-by":"crossref","unstructured":"Yamanaka, K., Demaine, E.D., Ito, T., Kawahara, J., Kiyomi, M., Okamoto, Y., Saitoh, T., Suzuki, A., Uchizawa, K., Uno, T.: Swapping labeled tokens on graphs. In: FUN 2014 Proceedings, pp. 364\u2013375. Springer (2014)","DOI":"10.1007\/978-3-319-07890-8_31"},{"key":"387_CR37","doi-asserted-by":"crossref","unstructured":"Yamanaka, K., Horiyama, T., Kirkpatrick, D.G., Otachi, Y., Saitoh, T., Uehara, R., Uno, Y.: Swapping colored tokens on graphs. In: WADS 2015 Proceedings, pp. 619\u2013628 (2015)","DOI":"10.1007\/978-3-319-21840-3_51"},{"issue":"14","key":"387_CR38","first-page":"1","volume":"2015\u2013AL\u2013153","author":"G Yasui","year":"2015","unstructured":"Yasui, G., Abe, K., Yamanaka, K., Hirayama, T.: Swapping labeled tokens on complete split graphs. SIG Tech. Rep. 2015\u2013AL\u2013153(14), 1\u20134 (2015)","journal-title":"SIG Tech. Rep."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-017-0387-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0387-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-017-0387-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,4]],"date-time":"2019-10-04T19:36:29Z","timestamp":1570217789000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-017-0387-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,20]]},"references-count":38,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2018,9]]}},"alternative-id":["387"],"URL":"https:\/\/doi.org\/10.1007\/s00453-017-0387-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,10,20]]}}}