Dissertação de Mestrado
DOI
https://doi.org/10.11606/D.45.2012.tde-22012013-160000
Documento
Autor
Nome completo
Juan Gabriel Gutierrez Alva
E-mail
Unidade da USP
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2012
Orientador
Banca examinadora
Feofiloff, Paulo (Presidente)
Lee, Orlando
Pina Junior, Jose Coelho de
Lee, Orlando
Pina Junior, Jose Coelho de
Título em português
O problema do multicorte dirigido mínimo
Palavras-chave em português
algoritmos em grafos
multicommodity disconnecting set.
multicorte dirigido
teoria dos grafos
multicommodity disconnecting set.
multicorte dirigido
teoria dos grafos
Resumo em 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 em inglês
The directed multicut problem
Palavras-chave em inglês
algorithms in graphs
directed multicut
graph theory
multicommodity disconnecting set.
directed multicut
graph theory
multicommodity disconnecting set.
Resumo em 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.
AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
multicorteJuanG.pdf (563.31 Kbytes)
Data de Publicação
2013-01-23
AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
CeTI-SC/STI
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2024. Todos os direitos reservados.
CeTI-SC/STI
Biblioteca Digital de Teses e Dissertações da USP. Copyright © 2001-2024. Todos os direitos reservados.