The token swap problem: polynomial time algorithms for graph classes and integer linear programming formulations
Carregando...
Arquivos
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Dissertação de mestrado
Título alternativo
O problema da troca de tokens: algoritmos de tempo polinomial para classes de grafos e formulações de programação linear inteira
Primeiro orientador
Membros da banca
Celina Miraglia Herrera de Figueiredo
Fernando Magno Quintão Pereira
Fernando Magno Quintão Pereira
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.
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.
Assunto
Computação – Teses, Arquitetura de computador – Teses, Teoria dos Grafos – Teses, Programação linear – Teses
Palavras-chave
Graph theory, Reconfiguration, Integer programming
Citação
Departamento
Endereço externo
Avaliação
Revisão
Suplementado Por
Referenciado Por
Licença Creative Commons
Exceto quando indicado de outra forma, a licença deste item é descrita como Acesso aberto