Use este identificador para citar ou linkar para este item:
http://repositorio.utfpr.edu.br/jspui/handle/1/37332| Título: | Preenchendo lacunas para a solução polinomial do Jogo da Inundação em grafos de co-comparabilidade |
| Título(s) alternativo(s): | Filling gaps in the polynomial-time solution for the Flood-it Game on co-comparability graphs |
| Autor(es): | Vinne, Jeremy Van Der |
| Orientador(es): | Almeida, Sheila Morais de |
| Palavras-chave: | Jogos de tabuleiro Representações dos grafos Algorítmos Complexidade computacional Board games Representations of graphs Algorithms Computational complexity |
| Data do documento: | 11-Fev-2025 |
| Editor: | Universidade Tecnológica Federal do Paraná |
| Câmpus: | Ponta Grossa |
| Citação: | VINNE, Jeremy Van Der. Preenchendo lacunas para a solução polinomial do Jogo da Inundação em grafos de co-comparabilidade. 2024. Trabalho de Conclusão de Curso (Bacharel em Ciência da Computação) - Universidade Tecnológica Federal do Paraná, 2024. |
| Resumo: | O Jogo da Inundação é um jogo em um tabuleiro (uma matriz 𝑚 × 𝑛) onde cada célula tem uma cor de um dado conjunto de cores. O objetivo é fazer com que todas as células tenham a mesma cor, com o menor número possível de movimentos. Os grafos que modelam o tabuleiro do Jogo da Inundação são chamados de grafos grades. Um grafo que admite orientação transitiva de suas arestas é um grafo de comparabilidade. Um grafo é de co-comparabilidade se e somente se é o complemento de um grafo de comparabilidade. Fleischer e Woeginger (2012) afirmam que o Jogo da Inundação pode ser resolvido eficientemente em grafos de co-comparabilidade. Porém, este resultado foi refutado por Lorenzi e Almeida (2021), que mostraram um contraexemplo onde o algoritmo não termina. Este trabalho preencheu algumas lacunas identificadas nos resultados de Fleischer e Woeginger (2012), fornecendo algoritmos para supri-las. Especificamente, exploramos a solução proposta por Fleischer e Woeginger (2012) para o Jogo da Inundação, considerando-a para grafos de co-comparabilidade com pivô minimal ou maximal. |
| Abstract: | The Flood-it Game is a game played on a board (an 𝑚 × 𝑛 matrix) where each cell has a color from a given set of colors. The goal is to make all cells have the same color with the minimum number of moves. The graphs that model the Flood-it Game board are called grid graphs. A graph that allows a transitive orientation for its edges is a comparability graph. A graph is a co-comparability graph if and only if its complement is a comparability graph. Fleischer and Woeginger (2012) claim that the Flood-it Game can be efficiently solved on co-comparability graphs. However, this result was refuted by Lorenzi and Almeida (2021), who showed a counterexample where the algorithm does not finish. In this project, we filled some gaps in Fleischer and Woeginger’s (2012) solution by providing algorithms to address them. Specifically, we explore the solution provided by Fleischer and Woeginger (2012) for the Flood-it Game, considering it for co-comparability graphs with minimal or maximal pivot. |
| URI: | http://repositorio.utfpr.edu.br/jspui/handle/1/37332 |
| Aparece nas coleções: | PG - Ciência da Computação |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| lacunasinundacaografoscocomparabilidade.pdf | 320,48 kB | Adobe PDF |  Visualizar/Abrir |
Este item está licenciada sob uma Licença Creative Commons
