Estudo poliedrico do problema do maximo subrafo induzido comum.

• Processo: 07/53617-4
• Modalidade de apoio: Bolsas no Brasil - Mestrado
• Data de Início da vigência: 01 de outubro de 2007
• Data de Término da vigência: 28 de fevereiro de 2009
• Área de 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
• Palavra(s)-Chave do Pesquisador: Combinatoria Poliedrica | Isomorfismo De Subrafos | Otimizacao Combinatoria | Programacao 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 Campinas, SP.