Algoritmo dual ascent distribuído aplicado ao Problema de Steiner em grafos

• Ano de defesa: 2010
• Autor(a) principal: Santos, Marcelo Costa Pinto e
• 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
• Palavras-chave em Português: Problema de steiner; Algoritmo distribuído; Grafo; Multicast; CNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAO::TEORIA DA COMPUTACAO::COMPUTABILIDADE E MODELOS DE COMPUTACAO
• Link de acesso: https://app.uff.br/riuff/handle/1/18766

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