Disertación de Maestría
DOI
https://doi.org/10.11606/D.45.2012.tde-22012013-160000
Documento
Autor
Nombre completo
Juan Gabriel Gutierrez Alva
Dirección Electrónica
Instituto/Escuela/Facultad
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2012
Director
Tribunal
Feofiloff, Paulo (Presidente)
Lee, Orlando
Pina Junior, Jose Coelho de
Lee, Orlando
Pina Junior, Jose Coelho de
Título en portugués
O problema do multicorte dirigido mínimo
Palabras clave en portugués
algoritmos em grafos
multicommodity disconnecting set.
multicorte dirigido
teoria dos grafos
multicommodity disconnecting set.
multicorte dirigido
teoria dos grafos
Resumen en portugués
O Problema do Multicorte Dirigido Mínimo é um problema clássico em otimização combinatória. Ele é NP-difícil mesmo para instâncias muito simples. Este trabalho faz uma análise dos algoritmos exatos e de aproximação para resolver o problema. Também implementa alguns desses algoritmos e compara seus desempenhos.
Título en inglés
The directed multicut problem
Palabras clave en inglés
algorithms in graphs
directed multicut
graph theory
multicommodity disconnecting set.
directed multicut
graph theory
multicommodity disconnecting set.
Resumen en inglés
The directed multicut problem is a classical problem in combinatorial optimization. It is NP-hard even for very simple families of instances. This work makes an analysis of the exact and approximation algorithms for the problem. It also implements some of these algorithms and compares their performances.
ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
multicorteJuanG.pdf (563.31 Kbytes)
Fecha de Publicación
2013-01-23
ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
CeTI-SC/STI
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2024. Todos los derechos reservados.
CeTI-SC/STI
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2024. Todos los derechos reservados.