| Processo: | 07/53617-4 |
| Modalidade de apoio: | 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 |
| 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) | |
| Matéria(s) publicada(s) na Agência FAPESP sobre a bolsa: | |
| Mais itensMenos itens | |
| TITULO | |
| Matéria(s) publicada(s) em Outras Mídias ( ): | |
| Mais itensMenos itens | |
| VEICULO: TITULO (DATA) | |
| VEICULO: TITULO (DATA) | |