Please use this identifier to cite or link to this item: http://www.repositorio.ufc.br/handle/riufc/14140
Title in Portuguese: Jogos de perseguição-evasão, decomposições e convexidade em grafos
Title: Pursuit-evasion games, decompositions and convexity on graphs
Author: Soares, Ronan Pardo
Advisor(s): Sales, Cláudia Linhares
Co-advisor(s): Coudert, David
Keywords: Teoria dos grafos
Jogos de aventura por computador
Convexidade
Issue Date: 2013
Citation: SOARES, R. P.; SALES, C. L.; COUDERT, D. (2013)
Abstract in Portuguese: Esta tese é centrada no estudo de propriedades estruturais de grafos cujas compressões permitem a concepção de algoritmos eficientes para resolver problemas de otimização. Estamos particularmente interessados em decomposições, em jogos de perseguição-evasão e em convexidade. O jogo de Processo foi definido como um modelo para a reconfiguração de roteamento em redes WDM. Muitas vezes, jogos de perseguição-evasão, em que uma equipe de agentes tem como objetivo limpar um grafo não direcionado, estão intimamente relacionados com decomposições em grafos. No caso de grafos direcionados, mostramos que o jogo de Processo é monotônico e definimos uma nova decomposição em grafos equivalente a tal jogo. A partir de então, investigamos outras decomposições em grafos. Propomos um algoritmo FPT para calcular vários parâmetros de largura em grafos. Em particular, este é o primeiro algoritmo FPT para calcular a largura em árvore especial e a largura em árvore q-ramificada de um grafo. Em seguida, estudamos um outro jogo perseguição-evasão que modela problemas de pré-obtenção. Nós introduzimos uma versão mais realista do jogo de Vigilância a versão on-line. Estudamos a diferença entre o jogo de Vigilância clássico e suas versões conectadas e on-line, fornecendo novos limites para essa diferença. Nós, então, definimos um modelo geral para o estudo de jogos perseguição-evasão, com base em técnicas de programação linear. Este método permite-nos dar os primeiros resultados de aproximação para alguns desses jogos. Finalmente, estudamos outro parâmetro relacionado com a convexidade e a propagação da infecção em redes, o “hull number”. Nós fornecemos vários resultados de complexidade computacional, dependendo das propriedades estruturais do grafo de entrada e usando decomposições em grafos. Alguns destes resultados respondem problemas em aberto na literatura.
Description: SOARES, R. P. Jogos de perseguição-evasão, decomposições e convexidade em grafos. 2013. 206 f. (Doutorado em Ciência da Computação) - Centro de Ciências, Universidade Federal do Ceará, Fortaleza, 2013.
URI: http://www.repositorio.ufc.br/handle/riufc/14140
metadata.dc.type: Tese
Appears in Collections:DCOMP - Teses defendidas na UFC

Files in This Item:
File Description SizeFormat 
2013_tese_rpsoares.pdf1,82 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.