{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:27:49Z","timestamp":1740144469682,"version":"3.37.3"},"reference-count":29,"publisher":"EDP Sciences","issue":"1","license":[{"start":{"date-parts":[[2024,2,19]],"date-time":"2024-02-19T00:00:00Z","timestamp":1708300800000},"content-version":"vor","delay-in-days":49,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002322","name":"Coordena\u00e7\u00e3o de Aperfei\u00e7oamento de Pessoal de N\u00edvel Superior","doi-asserted-by":"publisher","award":["88882.348155\/2019-01"],"award-info":[{"award-number":["88882.348155\/2019-01"]}],"id":[{"id":"10.13039\/501100002322","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003593","name":"Conselho Nacional de Desenvolvimento Cient\u00edfico e Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["406036\/2021-7","312069\/2021-9"],"award-info":[{"award-number":["406036\/2021-7","312069\/2021-9"]}],"id":[{"id":"10.13039\/501100003593","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004901","name":"Funda\u00e7\u00e3o de Amparo \u00e0 Pesquisa do Estado de Minas Gerais","doi-asserted-by":"publisher","award":["APQ-01707-21"],"award-info":[{"award-number":["APQ-01707-21"]}],"id":[{"id":"10.13039\/501100004901","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2023,9,1]]},"published-print":{"date-parts":[[2024,1]]},"abstract":"<jats:p>The reconfiguration framework models the concept of transformation of combinatorial objects under a variety of operations and constraints. When it comes to reconfiguration challenges, the questions of importance are connectivity, diameter and distance, which can be considered and restrained in many ways. This work focuses on the Token Swap problem, a reconfiguration problem with variations that even precede the systematic study of the reconfiguration framework. In this problem, the goal is to convert an initial token placement on the vertices of a graph into a target token placement with the minimum number of swap operations. The main result of this paper is the construction of a polynomial algorithm for threshold graphs and subsequently cographs.<\/jats:p>","DOI":"10.1051\/ro\/2023134","type":"journal-article","created":{"date-parts":[[2023,9,5]],"date-time":"2023-09-05T08:17:44Z","timestamp":1693901864000},"page":"441-455","source":"Crossref","is-referenced-by-count":0,"title":["Polynomial time algorithms for the token swapping problem on cographs"],"prefix":"10.1051","volume":"58","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9116-5801","authenticated-orcid":false,"given":"Caio Henrique Segawa","family":"Tonetti","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4608-4559","authenticated-orcid":false,"given":"Vinicius Fernandes","family":"dos Santos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7561-6825","authenticated-orcid":false,"given":"Sebasti\u00e1n","family":"Urrutia","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2024,2,19]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Aho A.V., Hopcroft J.E. and Ullman J.D., On finding lowest common ancestors in trees, in Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, STOC\u201973. Association for Computing Machinery. New York, NY, USA (1973) 253\u2013265.","DOI":"10.1145\/800125.804056"},{"key":"R2","unstructured":"Aichholzer O., Demaine E.D., Korman M., Lubiw A., Lynch J., Mas\u00e1rov\u00e1 Z., Rudoy M., Williams V. Vassilevska and Wein N., Hardness of Token Swapping on Trees, in 30th Annual European Symposium on Algorithms (ESA 2022). Vol. 244 of Leibniz International Proceedings in Informatics (LIPIcs), edited by Chechik S., Navarro G., Rotenberg E. and Herman G.. Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany (2022) 3:1\u20133:15."},{"key":"R3","doi-asserted-by":"crossref","first-page":"441","DOI":"10.1007\/s00224-004-1155-5","volume":"37","author":"Alstrup","year":"2004","journal-title":"Theory Comput. Syst."},{"key":"R4","doi-asserted-by":"crossref","first-page":"544","DOI":"10.1137\/0219037","volume":"19","author":"Annexstein","year":"1990","journal-title":"SIAM J. Comput."},{"key":"R5","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1137\/S089548019528280X","volume":"11","author":"Bafna","year":"1998","journal-title":"SIAM J. Discret. Math."},{"key":"R6","first-page":"1","volume":"24","author":"Biniaz","year":"2023","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"R7","doi-asserted-by":"crossref","first-page":"2656","DOI":"10.1007\/s00453-017-0387-0","volume":"80","author":"Bonnet","year":"2018","journal-title":"Algorithmica"},{"key":"R8","doi-asserted-by":"crossref","first-page":"1556","DOI":"10.1016\/j.jcss.2015.02.003","volume":"81","author":"Bulteau","year":"2015","journal-title":"J. Comput. Syst. Sci."},{"key":"R9","doi-asserted-by":"crossref","unstructured":"Erd\u00f6s P. and Rado R., A Partition Calculus in Set Theory. Birkh\u00a8auser Boston, Boston, MA (1987) 179\u2013241.","DOI":"10.1007\/978-0-8176-4842-8_14"},{"key":"R10","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"Harel","year":"1984","journal-title":"SIAM J. Comput."},{"key":"R11","doi-asserted-by":"crossref","first-page":"775","DOI":"10.1089\/106652703322539097","volume":"10","author":"Heath","year":"2003","journal-title":"J. Comput. Biol. J. Comput. Mol. Cell Biol."},{"key":"R12","doi-asserted-by":"crossref","first-page":"1054","DOI":"10.1016\/j.tcs.2010.12.005","volume":"412","author":"Ito","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"R13","doi-asserted-by":"crossref","first-page":"397","DOI":"10.2307\/2369492","volume":"2","author":"Johnson","year":"1879","journal-title":"Am. J. Math."},{"key":"R14","doi-asserted-by":"crossref","unstructured":"Kawahara J., Saitoh T. and Yoshinaka R., The time complexity of the token swapping problem and its parallel variants, in WALCOM: Algorithms and Computation. Springer International Publishing, Cham (2017) 448\u2013459.","DOI":"10.1007\/978-3-319-53925-6_35"},{"key":"R15","unstructured":"Knuth D.E., The art of computer programming, in Sorting and Searching, 2nd edition. Vol. 3. Addison Wesley Longman Publishing Co., Inc., USA (1998)."},{"key":"R16","unstructured":"Miltzow T., Narins L., Okamoto Y., Rote G., Thomas A. and Uno T., Tight exact and approximate algorithmic results on token swapping. Preprint arXiv:1602.05150 (2016)."},{"key":"R17","unstructured":"Mouawad A.E., On reconfiguration problems: structure and tractability. Ph.D. thesis, University of Waterloo (2015)."},{"key":"R18","doi-asserted-by":"crossref","first-page":"52","DOI":"10.3390\/a11040052","volume":"11","author":"Nishimura","year":"2018","journal-title":"Algorithms"},{"key":"R19","first-page":"124546","volume":"76","author":"Pai","year":"2020","journal-title":"J. Supercomput."},{"key":"R20","doi-asserted-by":"crossref","unstructured":"Razborov A., Proof complexity of pigeonhole principles, in Developments in Language Theory. Springer Berlin Heidelberg, Berlin, Heidelberg (2002) 100\u2013116.","DOI":"10.1007\/3-540-46011-X_8"},{"key":"R21","doi-asserted-by":"crossref","unstructured":"Siraichi M.Y., Santos V.F.D., Collange S. and Pereira F.M.Q., Qubit allocation, in Proceedings of the 2018 International Symposium on Code Generation and Optimization. ACM, New York, NY, USA (2018) 113\u2013125.","DOI":"10.1145\/3168822"},{"key":"R22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3360546","volume":"3","author":"Siraichi","year":"2019","journal-title":"Proc. ACM Program. Lang."},{"key":"R23","doi-asserted-by":"crossref","first-page":"92","DOI":"10.1006\/jcta.1998.2905","volume":"85","author":"Smith","year":"1999","journal-title":"J. Comb. Theory Ser. A"},{"key":"R24","doi-asserted-by":"crossref","first-page":"726","DOI":"10.1016\/j.jcta.2010.08.007","volume":"118","author":"Smith","year":"2011","journal-title":"J. Comb. Theory Ser. A"},{"key":"R25","doi-asserted-by":"crossref","unstructured":"van den Heuvel J., The complexity of change, in Surveys in Combinatorics. Cambridge University Press, Cambridge (2013) 127\u2013160.","DOI":"10.1017\/CBO9781139506748.005"},{"key":"R26","first-page":"129","volume":"30","author":"Vaughan","year":"1991","journal-title":"J. Comb. Math. Comb. Comput."},{"key":"R27","unstructured":"Wang L. and Tang K.W., The cayley graph implementation in tinyos for dense wireless sensor networks, in 2007 Wireless Telecommunications Symposium. 2007 Thyrrenian International Workshop on Digital Communication, Italy (2007) 1\u20137."},{"key":"R28","doi-asserted-by":"crossref","first-page":"81","DOI":"10.1016\/j.tcs.2015.01.052","volume":"586","author":"Yamanaka","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"R29","doi-asserted-by":"crossref","unstructured":"Yamanaka K., Horiyama T., Neil J.M., Kirkpatrick D.G., Otachi Y., Saitoh T., Uehara R. and Uno Y., Swapping colored tokens on graphs, in Workshop on Algorithms and Data Structures. Springer, Victoria, BC, Canada (2015) 16.","DOI":"10.1007\/978-3-319-21840-3_51"}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2023134\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,2,19]],"date-time":"2024-02-19T08:57:56Z","timestamp":1708333076000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2023134"}},"subtitle":[],"editor":[{"given":"M.B.","family":"Campelo Neto","sequence":"first","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"S.","family":"Klein","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"I.","family":"Loiseau","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"Y.","family":"Wakabayashi","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"A.","family":"Weintraub","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"V.","family":"dos Santos","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"T.","family":"Liebling","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"R.","family":"Mahjoub","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"N.","family":"Maculan","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2024,1]]},"references-count":29,"journal-issue":{"issue":"1"},"alternative-id":["ro230147"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2023134","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"2804-7303"}],"subject":[],"published":{"date-parts":[[2024,1]]}}}