Atenção:
O eduCAPES é um repositório de objetos educacionais, não sendo responsável por materiais de terceiros submetidos na plataforma. O usuário assume ampla e total responsabilidade quanto à originalidade, à titularidade e ao conteúdo, citações de obras consultadas, referências e outros elementos que fazem parte do material que deseja submeter. Recomendamos que se reporte diretamente ao(s) autor(es), indicando qual parte do material foi considerada imprópria (cite página e parágrafo) e justificando sua denúncia.
Caso seja o autor original de algum material publicado indevidamente ou sem autorização, será necessário que se identifique informando nome completo, CPF e data de nascimento. Caso possua uma decisão judicial para retirada do material, solicitamos que informe o link de acesso ao documento, bem como quaisquer dados necessários ao acesso, no campo abaixo.
Todas as denúncias são sigilosas e sua identidade será preservada. Os campos nome e e-mail são de preenchimento opcional. Porém, ao deixar de informar seu e-mail, um possível retorno será inviabilizado e/ou sua denúncia poderá ser desconsiderada no caso de necessitar de informações complementares.
Metadados | Descrição | Idioma |
---|---|---|
Autor(es): dc.contributor | Almeida, Sheila Morais de | - |
Autor(es): dc.contributor | Silva, Alane Marie de Lima Gonçalves da | - |
Autor(es): dc.contributor | Zatesko, Leandro Miranda | - |
Autor(es): dc.contributor | Aguitoni, Maria Cláudia | - |
Autor(es): dc.contributor | Omai, Mayara Midori | - |
Autor(es): dc.creator | Pereira, Bruno Henrique Silva | - |
Data de aceite: dc.date.accessioned | 2025-08-29T12:33:41Z | - |
Data de disponibilização: dc.date.available | 2025-08-29T12:33:41Z | - |
Data de envio: dc.date.issued | 2025-07-02 | - |
Data de envio: dc.date.issued | 2025-07-02 | - |
Data de envio: dc.date.issued | 2025-02-09 | - |
Fonte completa do material: dc.identifier | http://repositorio.utfpr.edu.br/jspui/handle/1/37333 | - |
Fonte: dc.identifier.uri | http://educapes.capes.gov.br/handle/capes/1097667 | - |
Descrição: dc.description | The 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.description | O 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.format | application/pdf | - |
Idioma: dc.language | pt_BR | - |
Publicador: dc.publisher | Universidade Tecnológica Federal do Paraná | - |
Publicador: dc.publisher | Ponta Grossa | - |
Publicador: dc.publisher | Brasil | - |
Publicador: dc.publisher | Departamento Acadêmico de Informática | - |
Publicador: dc.publisher | Ciência da Computação | - |
Publicador: dc.publisher | UTFPR | - |
Direitos: dc.rights | openAccess | - |
Direitos: dc.rights | http://creativecommons.org/licenses/by/4.0/ | - |
Palavras-chave: dc.subject | Jogos de tabuleiro | - |
Palavras-chave: dc.subject | Algorítmos | - |
Palavras-chave: dc.subject | Árvores (Teoria dos grafos) | - |
Palavras-chave: dc.subject | Board games | - |
Palavras-chave: dc.subject | Algorithms | - |
Palavras-chave: dc.subject | Trees (Graph theory) | - |
Palavras-chave: dc.subject | CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO | - |
Título: dc.title | O Jogo da Inundação em árvores | - |
Título: dc.title | Flood-it in trees | - |
Tipo de arquivo: dc.type | livro digital | - |
Aparece nas coleções: | Repositorio Institucional da UTFPR - RIUT |
O Portal eduCAPES é oferecido ao usuário, condicionado à aceitação dos termos, condições e avisos contidos aqui e sem modificações. A CAPES poderá modificar o conteúdo ou formato deste site ou acabar com a sua operação ou suas ferramentas a seu critério único e sem aviso prévio. Ao acessar este portal, você, usuário pessoa física ou jurídica, se declara compreender e aceitar as condições aqui estabelecidas, da seguinte forma: