Busca avançada
Ano de início
Entree

Estudo poliedrico do problema do maximo subrafo induzido comum.

Processo: 07/53617-4
Linha de fomento:Bolsas no Brasil - Mestrado
Vigência (Início): 01 de outubro de 2007
Vigência (Término): 28 de fevereiro de 2009
Área do conhecimento:Ciências Exatas e da Terra - Ciência da Computação - Teoria da Computação
Pesquisador responsável:Cid Carvalho de Souza
Beneficiário:Breno Piva Ribeiro
Instituição-sede: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brasil
Assunto(s):Otimização combinatória   Combinatória poliédrica   Programação linear inteira

Resumo

O projeto tem como tema o problema do máximo subgrafo induzido comum entre dois grafos não-orientados (MSIC). Este problema pertence à classe NP-difícil e, portanto, é pouco provável que haja algum algoritmo eficiente (i.e., polinomial) capaz de resolvê-lo. Contudo, dado o grande número de importantes aplicações do MSIC em diferentes domínios do conhecimento, é importante conhecer soluções exatas para instâncias do problema, mesmo que de porte pequeno. Isto permite um melhor entendimento da estrutura combinatória do problema, além de servir como guia para o desenvolvimento de heurísticas mais eficazes. Assim, o objetivo é estudar modelos de programação linear inteira para o MSIC, notadamente através de um enfoque poliedral, visando o desenvolvimento de um algoritmo branch-and-cut capaz de resolver exatamente o problema. Através de experimentos computacionais, pretende-se avaliar qual o tamanho da maior instância que se pode resolver a otimalidade quando se aplica este método. (AU)

Publicações acadêmicas
(Referências obtidas automaticamente das Instituições de Ensino e Pesquisa do Estado de São Paulo)
RIBEIRO, Breno Piva. Estudo poliedral do problema do maximo subgrafo induzido comum. 2009. Dissertação de Mestrado - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação.

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