Otimização em Grafos

Segundo Período de 2017
Pós-Graduação em Computação – IC/UFF
Professor Fábio Protti 

 

Horário e Local
Segundas e Quartas,11:00 -- 13:00

Sala 204

Avaliação

Consistirá de uma prova (formato a definir) + um trabalho de pesquisa/implementação (com apresentação de seminário).

 

Programa

Distâncias entre vértices: Busca em Largura

Caminhos mínimos: Dijkstra, Floyd-Warshall e outros algoritmos

Árvores geradoras: algoritmos de Kruskal e Prim, variantes de árvores geradoras

Árvores de Steiner

Emparelhamentos e Método Húngaro

Problema do Caixeiro Viajante

Problema do Carteiro Chinês

Fluxos em Redes

Colorações, Coberturas, Cliques e Conjuntos Independentes

Implementação de Problemas de Otimização em Grafos

 

Slides

 

Bibliografia

1. J. L. Szwarcfiter. Grafos e Algoritmos Computacionais. Campus, Rio de Janeiro, 1986.

2. Alan Gibbons. Algorithmic Graph Theory.  Cambridge University Press, 1985.

3. Cormen et al. Introduction to Algorithms. 3rd edition, MIT Press, 2009.

4. Ahuja et al. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.