CoordenaÃÃo de AperfeiÃoamento de NÃvel Superior / 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. / This thesis focuses on the study of structural properties of graphs whose understanding
enables the design of efficient algorithms for solving optimization problems. We are
particularly interested in methods of decomposition, pursuit-evasion games and the notion
of convexity.
The Process game has been defined as a model for the routing reconfiguration problem
in WDM networks. Often, such games where a team of searchers have to clear an
undirected graph are closely related to graph decompositions. In digraphs, we show that
the Process game is monotone and we define a new equivalent digraph decomposition.
Then, we further investigate graph decompositions. We propose a unified FPT-algorithm
to compute several graph width parameters. This algorithm turns to be the first FPTalgorithm
for the special and the q-branched tree-width of a graph.
We then study another pursuit-evasion game which models prefetching problems. We
introduce the more realistic online variant of the Surveillance game. We investigate the
gap between the classical Surveillance Game and its connected and online versions by
providing new bounds. We then define a general framework for studying pursuit-evasion
games, based on linear programming techniques. This method allows us to give first
approximation results for some of these games.
Finally, we study another parameter related to graph convexity and to the spreading
of infection in networks, namely the hull number. We provide several complexity results
depending on the graph structures making use of graph decompositions. Some of these
results answer open questions of the literature.
| Identifer | oai:union.ndltd.org:IBICT/oai:www.teses.ufc.br:7471 |
| Date | 08 November 2013 |
| Creators | Ronan Pardo Soares |
| Contributors | ClÃudia Linhares Sales, David Coudert, Rudini Menezes Sampaio, David Ilcinkas, Nicolas Nisse, Ioan Todinca, Dimitrious Thilikos |
| Publisher | Universidade Federal do CearÃ, Programa de PÃs-GraduaÃÃo em CiÃncia da ComputaÃÃo, UFC, BR |
| Source Sets | IBICT Brazilian ETDs |
| Language | English |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/doctoralThesis |
| Format | application/pdf |
| Source | reponame:Biblioteca Digital de Teses e Dissertações da UFC, instname:Universidade Federal do Ceará, instacron:UFC |
| Rights | info:eu-repo/semantics/openAccess |
Page generated in 0.01 seconds