Please use this identifier to cite or link to this item:
http://repositorio.ufc.br/handle/riufc/14140| Type: | Tese |
| Title: | Jogos de perseguição-evasão, decomposições e convexidade em grafos |
| Title in English: | Pursuit-evasion games, decompositions and convexity on graphs |
| Authors: | Soares, Ronan Pardo |
| Advisor: | Sales, Cláudia Linhares |
| Co-advisor: | Coudert, David |
| Keywords: | Teoria dos grafos;Jogos de aventura por computador;Convexidade |
| Issue Date: | 2013 |
| Citation: | 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. |
| Abstract in Brazilian 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. |
| URI: | http://www.repositorio.ufc.br/handle/riufc/14140 |
| Appears in Collections: | DCOMP - Teses defendidas na UFC |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| 2013_tese_rpsoares.pdf | 1,82 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.