Jogos de perseguição-evasão, decomposições e convexidade em grafos

Soares, Ronan Pardo

Please use this identifier to cite or link to this item: http://repositorio.ufc.br/handle/riufc/14140

Full metadata record

DC Field	Value	Language
dc.contributor.advisor	Sales, Cláudia Linhares	-
dc.contributor.author	Soares, Ronan Pardo	-
dc.date.accessioned	2015-11-25T13:04:50Z	-
dc.date.available	2015-11-25T13:04:50Z	-
dc.date.issued	2013	-
dc.identifier.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.	pt_BR
dc.identifier.uri	http://www.repositorio.ufc.br/handle/riufc/14140	-
dc.language.iso	pt_BR	pt_BR
dc.subject	Teoria dos grafos	pt_BR
dc.subject	Jogos de aventura por computador	pt_BR
dc.subject	Convexidade	pt_BR
dc.title	Jogos de perseguição-evasão, decomposições e convexidade em grafos	pt_BR
dc.type	Tese	pt_BR
dc.contributor.co-advisor	Coudert, David	-
dc.description.abstract-ptbr	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.	pt_BR
dc.title.en	Pursuit-evasion games, decompositions and convexity on graphs	pt_BR
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

Show simple item record