O Jogo da Inundação em árvores

Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorAlmeida, Sheila Morais de-
Autor(es): dc.contributorSilva, Alane Marie de Lima Gonçalves da-
Autor(es): dc.contributorZatesko, Leandro Miranda-
Autor(es): dc.contributorAguitoni, Maria Cláudia-
Autor(es): dc.contributorOmai, Mayara Midori-
Autor(es): dc.creatorPereira, Bruno Henrique Silva-
Data de aceite: dc.date.accessioned2025-08-29T12:33:41Z-
Data de disponibilização: dc.date.available2025-08-29T12:33:41Z-
Data de envio: dc.date.issued2025-07-02-
Data de envio: dc.date.issued2025-07-02-
Data de envio: dc.date.issued2025-02-09-
Fonte completa do material: dc.identifierhttp://repositorio.utfpr.edu.br/jspui/handle/1/37333-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/capes/1097667-
Descrição: dc.descriptionThe present work addresses the problem of the Flood-It Game applied to trees, a generalization of a game played on colored grids, where the objective is to make the grid monochromatic with the fewest number of flooding moves. Fleischer e Woeginger (2012) established that the decision version of the Flood-It Game is an NP-Complete problem, even when restricted to trees. Moreover, Fleischer e Woeginger (2012) presented a polynomial-time algorithm for the Flood-it Game on interval graphs. Considering such results, we explore the class of caterpillar graphs, which are interval graphs that are also trees, and show that the Flood-It Game has a polynomial-time algorithmic solution when restricted to certain trees. While these trees are not necessarily interval graphs, they possess special structural properties that allow the reduction of the problem to the case of interval graphs. The main contribution of this work is the development of a polynomial-time preprocessing algorithm that reduces the Flood-It Game on such trees to the case of interval graphs. This algorithm takes a colored rooted tree as input, identifies monochromatic substructures, and outputs smaller trees. After preprocessing, the trees are evaluated for compatibility as interval graphs, enabling the application of efficient algorithms, such as the one proposed by Fleischer e Woeginger (2012). The results presented pave the way for further research, such as applying this approach to other subclasses of trees or variations of the problem, including free pivots or graphs with different chromatic constraints.-
Descrição: dc.descriptionO presente trabalho aborda o problema do Jogo da Inundação aplicado a árvores, uma generalização de um jogo em tabuleiros coloridos, cujo objetivo é tornar o tabuleiro monocromático com o menor número possível de movimentos de inundação. Fleischer e Woeginger (2012) estabeleceram que a versão de decisão do Jogo de Inundação é um problema NP-Completo mesmo quando restrito a árvores. Além disso, Fleischer e Woeginger (2012) apresentaram um algoritmo de tempo polinomial para o Jogo da Inundação em grafos de intervalos. Considerando tais resultados, exploramos a classe dos grafos caterpillars, que são os grafos de intervalos que são árvores, e mostramos que o Jogo da Inundação tem solução algorítmica em tempo polinomial quando restrito a algumas árvores que não precisam ser grafos de intervalos mas têm propriedades estruturais especiais que permitem a redução do problema ao caso dos grafos de intervalos. A principal contribuição deste trabalho foi o desenvolvimento de um algoritmo de pré-processamento com complexidade polinomial, capaz de reduzir o Problema do Jogo da Inundação quando a entrada é uma destas árvores para o caso de um grafo de intervalos. Este algoritmo, tendo como entrada uma árvore colorida e enraizada, identifica subestruturas monocromáticas e produz árvores menores. Após o pré-processamento, as árvores são avaliadas quanto à possibilidade de serem tratadas como grafos de intervalos, permitindo a aplicação de algoritmos eficientes, como o proposto por Fleischer e Woeginger (2012). Os resultados apresentados abrem espaço para novas pesquisas, como a aplicação desta abordagem em outras subclasses de árvores ou em variações do problema, como jogos de inundação com pivôs móveis ou em grafos com diferentes restrições cromáticas.-
Formato: dc.formatapplication/pdf-
Idioma: dc.languagept_BR-
Publicador: dc.publisherUniversidade Tecnológica Federal do Paraná-
Publicador: dc.publisherPonta Grossa-
Publicador: dc.publisherBrasil-
Publicador: dc.publisherDepartamento Acadêmico de Informática-
Publicador: dc.publisherCiência da Computação-
Publicador: dc.publisherUTFPR-
Direitos: dc.rightsopenAccess-
Direitos: dc.rightshttp://creativecommons.org/licenses/by/4.0/-
Palavras-chave: dc.subjectJogos de tabuleiro-
Palavras-chave: dc.subjectAlgorítmos-
Palavras-chave: dc.subjectÁrvores (Teoria dos grafos)-
Palavras-chave: dc.subjectBoard games-
Palavras-chave: dc.subjectAlgorithms-
Palavras-chave: dc.subjectTrees (Graph theory)-
Palavras-chave: dc.subjectCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO-
Título: dc.titleO Jogo da Inundação em árvores-
Título: dc.titleFlood-it in trees-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositorio Institucional da UTFPR - RIUT

Não existem arquivos associados a este item.