Dados do Trabalhos de Conclusão

INSTITUTO MILITAR DE ENGENHARIA
ENGENHARIA DE DEFESA (31007015011P8)
PROBLEMAS EM GRAFOS DINÂMICOS: OUTERPLANARIDADE E APLICAÇÕES
GERALDO AVELINO DE OLIVEIRA NETO
DISSERTAÇÃO
10/08/2017

Algoritmos em grafos desempenham um importante papel na área de computação. Muitos problemas aplicados ao mundo real podem ser modelados como um grafo e resolvidos utilizando-se algoritmos que exploram propriedades pertencentes aos mesmos. Nesse trabalho, o interesse principal é enfatizar os algoritmos aplicados a grafos dinâmicos, ou seja, grafos que se modificam conforme o passar do tempo (nesses tipos de algoritmos, a solução para o problema evita com que seja necessário efetuar um novo cálculo de todas as informações acerca do grafo após determinada operação de atualização no mesmo). Mais especificamente, estamos interessados em algoritmos para realizar a manutenção da outerplanaridade (um grafo é outerplanar se é planar e possui uma imersão no plano, sem cruzamento de arestas, de maneira tal que seus vértices pertencem à face exterior) em um grafo dinâmico. Nesta dissertação implementaremos um algoritmo completamente dinâmico para resolver o problema da manutenção da outerplanaridade em grafos dinâmicos.

Algoritmos em grafos;Grafos dinâmicos;Outerplanaridade;Imersão planar
Graph algorithms play an important role in computer science area. Many problems applied to the real world can be modeled as a graph and solved using algorithms that explore the graph properties. In this work, the main interest is to emphasize the algorithms applied to dynamic graphs, that is, graphs that change over time (in these types of algorithms, a solution to the problem avoids the need to perform a new calculation of all information about the graph after an update on it). More specifically, we are interested in algorithms to perform the maintenance of the outerplanarity (a graph is outerplanar if it is planar and has an embedding, without crossing of edges, in such a way that its vertices belong to the external face) in a dynamic graph. In this dissertation, the implementation of an algorithm for maintaining outerplanarity in dynamic graphs is presented.
Graph algorithms;Dynamic Graphs;Outerplanarity;Embedding
01
150
PORTUGUES
INSTITUTO MILITAR DE ENGENHARIA
O trabalho não possui divulgação autorizada

Contexto

ENGENHARIA DE DEFESA
COMUNICAÇÕES E INTELIGÊNCIA EM SISTEMAS DE DEFESA
Algoritmos em Grafos

Banca Examinadora

CLAUDIA MARCELA JUSTEL
DOCENTE - COLABORADOR
Sim
Nome Categoria
LILIAN MARKENZON Participante Externo
PAULO FERNANDO FERREIRA ROSA Docente - PERMANENTE

Vínculo

CLT
Empresa Privada
Outros
Não