[pt] O PROBLEMA DE STEINER NA MÉTRICA RETILÍNEA: PROPRIEDADES, NOVAS HEURÍSTICAS E ESTUDO COMPUTACIONAL

• Ano de defesa: 2007
• Autor(a) principal: CID CARVALHO DE SOUZA
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: MAXWELL
• Palavras-chave em Português: [pt] HEURISTICA; [pt] PROBLEMA DE STEINER; [pt] METRICA RETILINEA; [en] HEURISTICS; [en] STEINER PROBLEM; [en] RECTILINEAR METRIC
• Link de acesso: https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=10236&idi=1; https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=10236&idi=2; http://doi.org/10.17771/PUCRio.acad.10236

[pt] Nesta tese faz-se uma extensa revisão bibliográfica sobre o problema de Steiner na métrica retilínea, destacando-se a aplicação do mesmo no projeto de VLSI. São descritas em detalhes várias heurísticas existentes na literatura para as quais estudam-se a complexidade computacional e a qualidade das soluções obtidas. Além disso, são estabelecidos novos resultados relativos ao comportamento de pior caso destas heurísticas. Propõe-se, ainda, duas novas heurísticas para o problema de Steiner na métrica retilínea para as quais são estudadas a complexidade computacional e a qualidade da solução, inclusive com a análise do pior caso. Uma grande quantidade de testes computacionais permitiu a realização de uma comparação do desempenho das diversas heurísticas implementadas, concluindo-se que uma das novas heurísticas propostas fornece, em média, soluções melhores do que aquelas fornecidas pelas demais heurísticas conhecidas na literatura.