The token swap problem: polynomial time algorithms for graph classes and integer linear programming formulations
| dc.creator | Caio Henrique Segawa Tonetti | |
| dc.date.accessioned | 2026-04-02T19:50:35Z | |
| dc.date.issued | 2022-02-21 | |
| dc.description.abstract | O framework de reconfiguração introduz o conceito de transformação em problemas computacionais, mostrando novas preocupações como resultado da necessidade de compreender estas mudanças sob uma variedade de operações e restrições. Esta dissertação estuda o problema de Token Swap, um tipo de tarefa de reconfiguração em que começamos com fichas distribuídas nos vértices de um grafo e buscamos movê-las até que cada ficha alcance o vértice alvo que lhe corresponde. O objetivo é realizar essa transformação usando o menor número possível de operações de troca. O principal resultado dessa dissertação é a construção das ferramentas matemáticas necessárias e da prova de existência de um algoritmo ótimo para grafos da classe threshold e, subsequentemente, cografos. Então, alguns trabalhos preliminares sobre modelos de programação linear inteira para os problemas de Token Swap e Parallel Token Swap também são apresentados, juntamente com o raciocínio por trás de cada restrição. | |
| dc.description.sponsorship | CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior | |
| dc.identifier.uri | https://hdl.handle.net/1843/2340 | |
| dc.language | eng | |
| dc.publisher | Universidade Federal de Minas Gerais | |
| dc.rights | Acesso aberto | |
| dc.rights | Attribution 4.0 International | en |
| dc.rights.uri | http://creativecommons.org/licenses/by/4.0/ | |
| dc.subject | Computação – Teses | |
| dc.subject | Arquitetura de computador – Teses | |
| dc.subject | Teoria dos Grafos – Teses | |
| dc.subject | Programação linear – Teses | |
| dc.subject.other | Graph theory | |
| dc.subject.other | Reconfiguration | |
| dc.subject.other | Integer programming | |
| dc.title | The token swap problem: polynomial time algorithms for graph classes and integer linear programming formulations | |
| dc.title.alternative | O problema da troca de tokens: algoritmos de tempo polinomial para classes de grafos e formulações de programação linear inteira | |
| dc.type | Dissertação de mestrado | |
| local.contributor.advisor-co1 | Sebastián Alberto Urrutia | |
| local.contributor.advisor-co1Lattes | https://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4770434Y0&tokenCaptchar=0cAFcWeA7UpLeh7HsUdhIx_8_ElaPH2GItKihAVaZU3CAuAi_qSs8Mh_tWjIGThSTFLr6ztKHLewMHFNIbZr0bT5Q17FntzZycAGdlOr6OvHrTXLWN0DZjIwmtBHftColcfkZB-IU9vHkuPc4zVffRyZ2SectQMUbda2_c2ORBZyN9E1rOTe4EjgBtJfzNBE5Jhh4dwq5RADGJmZzSLmUKR50Z0LBa3FRCmFpC9Y2h4deUq9bfeqE9YEFuBZg-Rmma5gi-lc9AGFzfTJXgbhHARsczf2K3EjbNIWAp6Zo3Py18uyV_5qPD3p9kM_tVhedwNu4F_D0iKaSRStdjpNeZzdWWxAU9e32lEPObuBaR6OG1Q255nC-4s5hnVfgQywcXp7mCbM-vpakysbcvG7Wy0q8UcJ8910sspipRM6iVEc6hnsWHoo_rLfHLmpMA3iNTMRpNyJzauUnwFERmWmNzW1Gje0FPSoZV7CUaNlWkjjYNAWN_E4F1tTvn-3QWPCOTPpnKvOeGWenfWv1sh61iSnwUXllQU6j1x2x4v70PjzwKTi6-JZX76OqUeiP2ABj-cz5frqXhzgpSKrtjFfmzOltmjKKKEykr-ePsQQBie0stqd5aUJw1ryVzThatsRdzOqJz4Ay-W_DuxAStEUcvjrBK7wL_pCFZ2mKR8dmTZ3bPtyoYQWghCDBawRrWl3yELkfILDqTZcQu5pY9nGhDh8St4vI-9oNylWcHlyptf_CykJ-EGntC_BAEBZQNNU9vz_AL3hSLnDVn4cx8tCYSxn5tDJbnzVW0pzDjcmdkwrDQKmpfGZMgcsOI5m2AOCHbax_aoo5uTcr_WAkHkETTwjebdqhZJWJS55OWNF-_-e0MPhttkdaj06Oe2SsAxSmY8oys-K9iIGx8WLRctt6SnJqEm7eTz0XMR0K0a0kcwPhzUjgrYNIFMkV7xloCeK9SNXQIsDCxYetf4Yj9Fz5X6HaHKSp9BGItybxv701C0e3OlAeIb8T4yI8LpIeH4lK4xwjxlFofsNpBxSVERCtXnIhT8E_v9I-MXgV6XrHFuyP_a9L-OeZ3HyMm08irq0up-PfIRFVOLsw8wLV13Rq-ByS_7ns83RkL7s8Ywwllg0bKDKoZQ0V0XKbKn78ESly6UJIDpU-PzmJxpa82vwbA5JC_nsxRyAYbC_1NKCNhW8W3SxPT75h5rZY_yYrPdTWBcNDtPwU_y4X_d6ml912mo8oSYgr0r26YCyQ9wFnnskvDsTI-Z6K2pYwBty4OV5ZaVm_tf9v-OfVwgQeb-HgYWznkq2I59-ew4hJ0_R53i-tDbhW3j0Nm1y3oz6E__VJYiD5Jn9mF_pd84_gBKrMMBMFf22Vk7nyXYBQM7j0ECGjqCye_7-43VQcT7goVSCJHeVWMqaCjo0x35wuv3YNs2vZ8BGYEfCMQG3KaiemIKzgMgvM1EKazU-MUh-5poI1eJhaiaGVtQidGrRaYLzIIyC_HiVLR8EuHuWM6gFVseePpjwd-CA1YJQqdYwXAw2V9lrqao-bgmMxOfqyVSiVWXmzH2Ss9duDIeZqzX-T638gHZUwTSTNxy4-ihckOYLT-BQ1lxsm2pCGwy7wP8huo5ngHuEPtGY6J5DG4KarwBU3Fdz8wTlOrXOIhWTmWl7eDMPuIna8VHOiqCdEmwLmH3MuiaBSwHGep3DieKrwDe49iBiDy9XEulCP-96_6QoWkLf1i95RyK4X9p8_4RzP2HBwdAJ2UvRcrpkHKdNT01EucS-nAuSUCi8TEScaYPuYU0B6XYJbXgfIW-4bwUrL0Kq_Nn0CTkFFluU2uiL_EdZRG1d8js5hgzpttCfYqdpDB9fVTNl9MIR9eYfm_C3fjxtiv4jrSO_WvlbWpjJkKJbBL28y_oaOgMksPPIPub08FFZUTSwCHyiVO9xPrrh7JQQ6lIEMx-r-mI0qXu2h1jLKNc0Z3loRjin_8G3IK0rmZSDs5tZEShOxa_NBY2sGGO5nslbrWGkPCNx2FvBKDDV51JL-cEewdn9gdoQJ6ot9PvH1DXoIj2_-k2gDMG9ZjA2EIFK3Far1d9jDurx_FRgNcGVeGs7sGQ6w | |
| local.contributor.advisor1 | Vinicius Fernandes dos Santos | |
| local.contributor.advisor1Lattes | https://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4756555E8&tokenCaptchar=0cAFcWeA63d5RsM9q9wajCYXoNIDy2HLmZJK8CjxZOCcBN5XLdaPVriDWKSLsyqPUgvE0L7GvwkPi0cowYF54wp3DuH6-wEj4C40ajTsyt_It2Q2BfbFY8R4V-8SS_Pwh72kgeMTuFNujaOTuFhCqzaQcIPbtBrYezJWvuLQhna2_bGqQejqsvZcarw-fV21BW3TKGKnkf9Py2-X5oEDEbhr02_BeEcLKEaQ2IsStYbeDRuLEBT4vDIwmNlFqcXl3Q1scWPxZa02AssE2BkIY46GsWRksA7RmwzhIbJzVVNpgq-zRQpjsZlEtKM8_8UTSs05f8JPa-HtJrtkUwEJgGHon7oBS84l90A6SDA54m3Rd9ygp2eZfYMOlI7aD6oq7SnaaisLnXO_oH4x8hKFRMMV4dQjm8Bo1_xiVGWNpHeA3DUFnYLi2DYGfMnhXcQwxcCPDpy-IRcgC8osj2IdJEWj5It3xQM7Wh6I6ZYqgmaJcj8PM9IgNeTu_liPeLqqcDsfSG84k8f8_EupLvIUAqQ2ug45dn-vf-RHiKYzCyjc4rR5q_JHUZNDsO7fPb9r67SoF8rhGoE-4anZq6ySMJRzJVlSahhIuGn_yg_e2RdPeCcZJeXr2Ty1KUuRGpl4vxwXXkjaYw_Q5Iv2BfaSYq9QRw6T3PwjgVCDH0jWac60HUWxIimT50GKXRzwSwiLq3HzkAjm6goOPVJfUaFfasVi1g_jCv7C8jsgz67EaAXbSgXuL9TWbzuUBU0mmsSwKOTbdHBJdDRoS64eSmtghJzNFMG578HqUWHkOp-IARc54z7QhswJcT07DeoibCo04VzF75CtbL7EWuudQ3KxEHcU-xYCKUApqeMs6TgBxp2mKN5QE6zhMeenSxeJWzFt3zi5LTzNkRXc2ubfJT9ApKRkGZyGsvaGB1rh6_u4-zPUL7WDp_tw6Gt4q0DmYuPTO8tIKwNXgINkVUOT2xPJBs8Z0dkMWwd4-kHY4QhgIOY_4oj0kFLmQ6NVf94-sMiN4mTRixkk3XWcJQOpfrdgO5gaseYkc6xr9r6AUQPWZ7bnREZ23k-QrIR903Y75CIgIfUiX-u0O7UD-sMhogGslMyMEevY4xbKxkrNnu94ebGLKgXn-oxmUxSLWf0xd-8ifFizHfwvbMYt5Sh_P126PFqajVmW3jNg8mGhmOjy9uCJb99lxSzpqwCv6cy6HUxJkcxorBE9b8FTpeLBJkt6dcvIwfCjJA-zwW20WHt8BXl-ng8v-0pGk4xTNNemUOQ_Vu8UPrIP006DjnXGrxf0yQxfIMwMeRurNh2xf67qOfR29AzP463HctkLFOGPPXx0as62NO-VdbTXnMrM1rve5F1gYE7sEAzvnKMIYxcPPXp966P8TchgwmTe1IYspqn5eX6NpmGfTyAY5kM8rYCOdj8Lv6HhB2bf6qqV1S9lyZ3YzA1iGmwq40GPL-Fv_sL784fPRZ0XP0wQdzyG-SPVqBWW_BZHD2tUAksd2oGnKyT_ZrAw9rYSMDUR8eYIF_WThJECJQOERu_zt9755zjsguXsUaCaRjvmm3WzkikbdGwI6adt2_o1w6PvAmOtg2braeucAw2Vsw5Cjb7Efjvv1ouFSLR_v6VMocxL-ZhQT-_6_I3S-7D1Qd7a9kTWGyL7kExyW66PdPBBqEIet9HkqWao_9Y1Npt_YlWXWmNpZY1LOD8TzwHZz-tJtxQSol_aUXxV_dz2tbKDJ7gqE3L06_pb9mMMjrkLRI0E-yXCIBtAFQNXMZ0AVMIYRBb2M-zjwInYvg7lBSfIdTvGxnpJPJhkLPX8ew6klKIe_ZT2AFpBfN-GThbiYy9bXjF8Mjzy5NxFnHcZ_lEMvDsa9kvWh7KRxkZq5rwy9DtL9julhWAq5bPCsYWLB4teb0LBz42xPKkrCsZPbGOx6Cybia69fMswokBN5PU1zAvrr1Y-ENov_HPU0giAAbmQqqwVjyUfdLshtqqaiBVhu7twzJx97fEh9LmCZAxyalHiVpX_xArhZ5r_3y9yPNBTcFjOwmOx8_3qqM86FmbfX6IWqtoIXxxGR4UYESAaukmeQfNKW6I1lK-Nj5YJDNd_B5ufqu0ZEbnm7pY2B006N52uG3UYW-hv64GcLd2jUZ9rbT7Xqi1gN2LKbMDs-UownB6tGI8ZblN2Ew4xzkpLUo3KoRol82m5FxLGcx6GmXbA | |
| local.contributor.referee1 | Celina Miraglia Herrera de Figueiredo | |
| local.contributor.referee1 | Fernando Magno Quintão Pereira | |
| local.creator.Lattes | https://buscatextual.cnpq.br/buscatextual/visualizacv.do?id=K4302751Y8&tokenCaptchar=0cAFcWeA6co0CNReQQIC9fc74GDl_yEqwZrLN0N71HWjBexfV39OzL8s113YrWtNsR7Xg2Y_mLRvbVe9YekNGOhnyNMMvAjlE2ORjOcyCwfELzXMlFAx53f854mkatRY381bRfediFtrP9wWdNJVYg5ixmklcUS05_25QeMzzmOXqc8RnbUSMmgKOcUj_PoGsRUcfovT4lmGlDsXXtfh3Hm3-b61-vEethD6mA0tcD_Op8ZLfMDaXpxCR5PKDmDUzHnKvSxfbWdCbmMBSaOqa_zSZtZIPYsFUkInncJIvj9m1-kjBq8ZfdKmJRHiFiKO1Dp6WVUM7YdylWNgBiZN_U6_Y_4HWoyrsm5E6Gv9dFDGK5brhUirnA_avIAzDi-6Ef-m5JDjF-MvS8ztzi-fHGvJOqAL5jU1t0YZxo4SJf702_buKA9SxY8rzSDC8drOAEWaWszz69MxBAzsGW16Aqn_12v2xaARxoqbu85XzZsVS1J6OtKzBXae98wFwu78En3VxLT9qSLSDxgWxozarAVTDIGL1Yvx_uUBxz2F3mvDwLqk_ay4fqGIzApWbSk6sQQbsCtGIQU2OgoLmLnTtovVd_bX-XtJnCjvTXZWRKvtfpNg_SUHWHmboDGDevbvbBnfIbZNN6WsKtpG84Fmx1mohvGmCWaSAEEHbE3yt9NP4tosmCfJslS-7oBWg85UNOl01vUAWos41lxY5fyBHGpALabxKJbVTwAzXEDzXxjFYQu4cuZvl8649D6OOOnSCNoK3YkF6WplpoiM5rwPAe5s2ehTpIQKUl1boJvND1_SX_EJCX6WYjtpxREuA9S9vA4GC0jgrnexMgG9gxiRyXE9LXqXvTlK8ybljiycWedZPoelyTejoU95-sXI_QP-JYTbrp7svjN4df6dG7d-0TrnHdWqypraWwU-qopaULOg4lGnFRBCDwwdcHmjiMD_kDP00y1P1lu7P4P4UFtslbkUwSR1gfcJs6qA5wbXOyMdX8ZQ2rr3uEytzyd08g0QgieC8wH6CtN3fV0Yaonohjjg_k1OcjgC_Jw-OgRxvg1Z-nJGEJCJT4N236P2WynfQDWm1HtXx4Rd5PUE_79VYke9C827l1U7lwAPfMk7wo4tcXkktVJq--ldlxBKzKj5xW5ah_5shCGu8qzCH41A4iufHwmigurF7RsE34cvr8K1GBRpxDdAm5b_Fhb6dHzfIECm6vv2ONLVAvjoJ7l2GtWeiM3nGCd2w5ICtELCNrqC_-Nzm3WhgX__sMqwepQlFIHe4h2_O8jWBb5IWihaOto0UCLz5MKuAiCP0rPC4sp7EZ_WfKOiwbgZqNHxZWm1cO4wyFTjxSJyyn3elwi_R3j_2QW0qb1C8WU2eOThqrMcGbn09QahJ6P1QwSBvyvofP8hLS2MoeblgYP1EnxIusuzuLdAx5EEvAnyGngWTjCHoGUDqwIt1wr9tMfTSXXLxcNq3jgnm2bR6qFUMBTkqSINr7XWU5J9TC42MzjJx7tNfae_wEfbVT03IS3QNDRfrBdXHN4zGuZC2KwGERizjqCwwLIkQ3cc_cNjby0EAHNp4VszQU4aKPVHUwffI4uxxj8ZiB9DUB1koTYJaWvzuXb8C9c4L2c-xlxpkjZhw4hDkQtBFURNh4zNwOYlALztw851ePfLosLLIvdKYQdcgn1c04LTtN-3SBvwtEmdBP1uudOzmPeo1OaP76BQYgUu0LUhu82eb718tcRXQBmD-xoHbOmVh-fPficqUpFiDhygYK-uT0XbYteI0_MIkDYLtnxO9vQ5fSZyhCIg0O5037nSfDIM97hBGYiYLzJJ03mTkNrSDQ36wghTYz4mo5IU3JXLeI74W_MmiBtmbAsOFWQDYQ4ESGqTigLcQbkH-Hn2NNUnOzthdEOfmN-0Qm4btX20rZxDY8EM0JZhFld8-lA0zJjUw5sCKqcWzTyLfG5rG7GD138DqL48WFa6n08-jjf1hYiHzaWIVRydni18ypX8sU3geBhAGi-KGHlDlQBRtRsgiKNTn8sYNPYWcM0eZd2RoUyfc5w7c6kXvLoqJNLQYouyfuyBNVDA | |
| local.description.resumo | The reconfiguration framework introduces the concept of transformation into computational issues, posing new concerns as a result of the need to comprehend these changes under a variety of operations and constraints. This dissertation studies the Token Swap problem, a type of reconfiguration problem in which we start with tokens placed on the vertices of a graph and aim to move them so that each token ends up on its correct target vertex. The objective is to achieve this using as few swap operations as possible. The main result of this dissertation is the construction of the necessary mathematical tools and the proof of existence of an optimal algorithm for the class of threshold graphs and subsequently cographs. Then, some preliminary work on integer linear programming models for the problems of Token Swap and Parallel Token Swap will also be presented, together with a simple reasoning behind each constraint. | |
| local.identifier.orcid | https://orcid.org/0000-0001-9116-5801 | |
| local.publisher.country | Brasil | |
| local.publisher.department | ICX - DEPARTAMENTO DE CIÊNCIA DA COMPUTAÇÃO | |
| local.publisher.initials | UFMG | |
| local.publisher.program | Programa de Pós-Graduação em Ciência da Computação | |
| local.subject.cnpq | CIENCIAS EXATAS E DA TERRA |