Problemas combinatorios de congestionamento

AUTOR(ES)

Arlindo Flavio da Conceição

DATA DE PUBLICAÇÃO

2000

RESUMO

Nesta dissertação estudamos o aspecto combinatório dos problemas de congestionamento. O principal problema estudado consiste em, dado um grafo G e um inteiro positivo k, encontrar k árvores espalhadas de G, não necessariamente disjuntas, de peso total mínimo. Neste problema o congestionamento é caracterizado por funções que penalizam o peso de uma aresta se ela é usada por mais de uma árvore. Roskind e Tarjan apresentaram um algoritmo para a versão deste problema onde as árvores devem ser disjuntas nas arestas. Nós apresentamos uma descrição detalhada do algoritmo de Roskind e Tarjan e então mostramos um algoritmo polinomial para o problema de congestionamento, o algoritmo consiste em uma redução ao problema disjunto. O nosso algoritmo é quadrático em k. Apresentamos ainda duas heurísticas de complexidade linear em k. Baseados na mesma técnica, desenvolvemos algoritmos polinomiais para problemas combinatórios de congestionamento relacionados aos problemas de encontrar um caminho mínimo e de encontrar um emparelhamento de custo mínimo

ASSUNTO(S)

algoritmos otimização combinatoria arvores (teoria dos grafos)

Documentos Relacionados

• Problemas de alocação de tráfego sujeitos a congestionamento
• Algoritmos combinatorios para a logistica de distribuição
• Congestionamento e preço : o papel da tarifação como instrumento no controle do congestionamento em redes de computadores por chaveamento de pacotes
• Arranjos combinatórios: a charge nos estratagemas de construção da identidade do jornal
• elGen: ferramenta para geração de circuitos combinatórios e sequenciais para benchmark