Busca avançada
Ano de início
Entree

Implementação e teste de algoritmos de aproximação para o problema de Steiner com grupos

Processo: 03/10045-0
Linha de fomento:Bolsas no Brasil - Mestrado
Vigência (Início): 01 de março de 2004
Vigência (Término): 31 de agosto de 2005
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Matemática da Computação
Pesquisador responsável:Carlos Eduardo Ferreira
Beneficiário:Fernando Mario de Oliveira Filho
Instituição-sede: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brasil
Assunto(s):Algoritmos de aproximação   Otimização combinatória   Combinatória poliédrica   Branch-and-cut   Problema da árvore de Steiner

Resumo

O problema de Steiner com grupos consiste em, dado um grafo G com custos nas arestas e uma coleção R de grupos de vértices, encontrar um subgrafo de G que conecte pelo menos um vértice de cada grupo de R e que tenha custo mínimo. O problema é NP-difícil por ser uma generalização do problema de Steiner em grafos. Diversos algoritmos de aproximação foram propostos para este problema. Nosso objetivo é implementar estes algoritmos e fazer uma análise empírica da qualidade das soluções que eles fornecem. Para tanto, precisaremos também de um algoritmo exato para o problema que encontre o valor ótimo ou pelo menos bons limitantes inferiores para este valor. Pretendemos também, depois desta análise, incorporar os melhores algoritmos de aproximação em nossa abordagem exata para resolver o problema. (AU)

Publicações científicas
(Referências obtidas automaticamente do Web of Science e do SciELO, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores)
FERREIRA‚ C.E.; DE OLIVEIRA FILHO‚ F.M. Some formulations for the group steiner tree problem. DISCRETE APPLIED MATHEMATICS, v. 154, n. 13, p. 1877-1884, 2006.

Por favor, reporte erros na lista de publicações científicas escrevendo para: cdi@fapesp.br.