1. Repositório Institucional UFC
2. CC - Centro de Ciências
3. DCOMP - Departamento de Computação
4. DCOMP - Teses defendidas na UFC

Tipo:	Tese
Título :	Jogos de perseguição-evasão, decomposições e convexidade em grafos
Título en inglés:	Pursuit-evasion games, decompositions and convexity on graphs
Autor :	Soares, Ronan Pardo
Tutor:	Sales, Cláudia Linhares
Co-asesor:	Coudert, David
Palabras clave :	Teoria dos grafos;Jogos de aventura por computador;Convexidade
Fecha de publicación :	2013
Citación :	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.
Resumen en portugués brasileño:	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
Aparece en las colecciones:	DCOMP - Teses defendidas na UFC

Los ítems de DSpace están protegidos por copyright, con todos los derechos reservados, a menos que se indique lo contrario.