Algoritmo dual ascent distribuído aplicado ao Problema de Steiner em grafos
Ano de defesa: | 2010 |
---|---|
Autor(a) principal: | |
Orientador(a): | |
Banca de defesa: | |
Tipo de documento: | Tese |
Tipo de acesso: | Acesso aberto |
Idioma: | por |
Instituição de defesa: |
Programa de Pós-Graduação em Computação
Computação |
Programa de Pós-Graduação: |
Não Informado pela instituição
|
Departamento: |
Não Informado pela instituição
|
País: |
Não Informado pela instituição
|
Palavras-chave em Português: | |
Link de acesso: | https://app.uff.br/riuff/handle/1/18766 |
Resumo: | Apresentamos neste trabalho uma versão distribuída para o Algorítmo Dual Ascent, cuja versão sequencial foi proposta por [Wong, 1984] e tem se mostrado uma eficiente heurística para solução do Problema Steiner em Grafos. Estamos interessados no desenvolvimento de boas heurísticas para este problema porque o roteamento multicast pode ser modelado como um problema desta classe. Várias aplicações como jogos on-line, bate-papo em tempo real, vídeo conferência e banco de dados distribuído, que dependem do roteamento multicast eficiente estão sendo mais utilizados com a expansão da internet. O algorítmo apresentado provê meios para obtenção de uma boa solução para o problema com grafos orientados e não orientados, além de fornecer um limite inferior de excelente qualidade, tipicamente 3% abaixo do ótimo, que pode ser utilizado para avaliação de soluções obtidas com o Dual Ascent ou quaisquer outras heurísticas. Apresentamos também adaptações para a variação do problema com limitação de saltos, utilizado para modelar situações em que limitações de QoS sejam importantes e para a versão on-line, quando devemos adaptar a solução à inclusão e exclusão de nós nos grupos de terminais |