Otimização em Grafos

Código: PINF7020
Curso: Doutorado em Ciência da Computação
Créditos: 3
Carga horária: 45
Ementa: Introdução aos Problemas de Fluxo em Redes: Modelo Geral de Fluxo de Custo Mínimo, Subproblemas e Aplicações.
* Ferramentas Básicas de Grafos: Algoritmos de busca e Ordenação Topológica. Problemas de Caminhos Mínimos: Caracterização, Aplicações e Algoritmos de Rotulação.
* Problemas de Fluxo Máximo: Caracterização, Aplicações, Procedimento Básico do Caminho de Incremento de Fluxo,
* Algoritmos de Rotulação,
* Teorema básico de Max-Flow e Min-Cut e suas implicações combinatoriais. Problema de Fluxo de Custo Mínimo: Condições de Otimalidade, Dualidade, Algoritmo de Cancelamento de Ciclos.
Bibliografia: * Ahuja, R.K., Magnanti, T.L. and Orlin, J.B. (1993) . Network Flows: Theory, Algorithms, and Applications, ed. Prentice Hall.
* Bertsekas, D.P. (1998) - Network Optimization . Continuous and Discrete Models, ed. Athena Scientific, Belmont, Mass. USA.