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

AUTOR(ES)

CID CARVALHO DE SOUZA

DATA DE PUBLICAÇÃO

1989

RESUMO

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.

ASSUNTO(S)

heuristics metrica retilinea steiner problem rectilinear metric problema de steiner heuristica

Documentos Relacionados

• New heuristics to crew scheduling problem
• Novas heurísticas para o problema de escalonamento de atripulações
• Novas heurísticas para o problema de geração de escalas de jogos para torneios esportivos
• NEW HEURISTICS FOR THE PROBLEM OF CLIQUE PARTITIONING OF GRAPHS
• Novas heurísticas para o problema de geração de escalas de jogos para torneios esportivos