Otimização em Grafos
Primeiro Período de 2018
Pós-Graduação em Computação – IC/UFF
Professor Fábio Protti
Horário
e Local
Segundas e Quartas, 9:00 -- 11:00
Avaliação
Consistirá
de uma prova (formato a definir) +
um trabalho de pesquisa/implementação.
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
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.