Data/hora: 01/06/2024 15:21:34

Biblioteca(s): | Embrapa Unidades Centrais.
Data corrente: | 22/09/1997
Data da última atualização: | 12/12/2007
Autoria: | PACHECO, O. I. P.
Afiliação: | CNPTIA.
Título: | Contribuição para a resolução do problema de steiner num grafo direcionado: um método heurístico.
Ano de publicação: | 1985
Fonte/Imprenta: | Rio de Janeiro: UFRJ, 1985.
Páginas: | 132p.
Idioma: | Português
Notas: | Tese Metrado.
Conteúdo: | No presente trabalho desenvolvemos um método heurístico para resolver o problema de Steiner num grafo direcionado. Para isto, consideramos o problema de Steiner como sendo um problema de arborescencia geradora e de fluxo com custos fixos. Considerando uma definição particular de peso de uma arborescencia, formulamos o problema como sendo um problema de arborescencia geradora de peso mínimo, cuja solução contém a solução para o problema de Steiner. O método heurístico, desenvolvido para resolver este problema, foi implementado, em FORTRAN IV, em duas versões: na primeira considera-se qualquer arborescencia geradora incial e na segunda utiliza-se uma arborescencia geradora obtida a partir da solução dada pela heurística de Richard T. Wong, também implementada. O método heurístico mostrou-se sensível a arborescencia geradora inicial tanto no tempo empregado como na solução obtida. Os resultados obtidos foram considerados muito bons, especialmente pelas perspectivas que existem de se melhorar ainda mais o desempenho do método.
Palavras-Chave: | Análise de dado; Computação; Computation; Data processing; Geometria; Processamento de dado.
Thesaurus Nal: | data analysis.
Categoria do assunto: | --
Registro original: | Embrapa Unidades Centrais (AI-SEDE)
Exemplares: | AI-SEDE - (4645-1) - EMB - TS - -- - 85/021 - PAC - 1985.00021 - DIS