Return to search

[en] THE STEINER PROBLEM IN RECTILINEAR METRIC: PROPERTIES, NEW HEURISTICS AND COMPUTATIONAL STUDY / [pt] O PROBLEMA DE STEINER NA MÉTRICA RETILÍNEA: PROPRIEDADES, NOVAS HEURÍSTICAS E ESTUDO COMPUTACIONAL

[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. / [en] In this dissertation we present a survey about the Steiner
problem in the rectilinear metric, illustrating its
applications to the VLSI desing. A large number of
heurístics already described in literature is studied in
details. Moreover, we study the complexity of these
heuristics and the quality of their solutions. New results
concerning their worst case behavior are stated. We also
propose two new heuristics for thew Steiner problem in the
rectilinear metric, for which we study the complexity and
the quality of the solutions, including the worst case
analysis. A large nember of computational experiments was
conducted and allowed the comparison of the performances
of the heuristics implemented. We conclude from these
experiments that, in the average, the solutions obtained
by one of the new heuristics are better than the solutions
obtained by those alreafy available in the literature.

Identiferoai:union.ndltd.org:puc-rio.br/oai:MAXWELL.puc-rio.br:10236
Date03 August 2007
CreatorsCID CARVALHO DE SOUZA
ContributorsCELSO DA CRUZ CARNEIRO RIBEIRO, CELSO DA CRUZ CARNEIRO RIBEIRO
PublisherMAXWELL
Source SetsPUC Rio
LanguagePortuguese
Detected LanguageEnglish
TypeTEXTO

Page generated in 0.002 seconds