Cid C. de Souza
IC-UNICAMP
Sexta-feira, 1 de junho de 2007, 14:00
Anfiteatro do NUMEC-USP
Resumo:
Nesta palestra será discutido o seguinte problema relacionado ao isomorfismo em grafos: dados dois grafos $G$ e $H$ com o mesmo número de vértices, encontre um subgrafo comum a $G$ e $H$, não necessariamente induzido, cujo número de arestas seja máximo.
Trata-se de um problema NP-difícil cujas aplicações práticas incluem a alocação de tarefas a processadores em um ambiente de Computação Paralela.
Estudos deste problema usando Programação Linear Inteira e Combinatória Poliédrica vêm sendo realizados há alguns anos por J. Marenco e J. Marenco e I. Loiseau. Estes trabalhos apresentam uma grande quantidade de resultados sobre facetas e desigualdades válidas associadas à envoltória convexa das soluções inteiras do programa linear. Contudo, são poucos os relatos de experimentos computacionais com estes resultados e os que estão disponíveis não permitem uma análise aprofundada sobre as dificuldades de resolução exata do problema.
Nesta palestra apresentamos o trabalho que temos feito para entender melhor as desigualdades propostas por Marenco e o seu efeito computacional quando usadas em um algoritmo de branch-and-cut.
Faremos algumas análises preliminares dos resultados que obtivemos até aqui, apontando possíveis direções de pesquisa que permitam vencer os obstáculos que estamos enfrentando.
Este trabalho está sendo feito em conjunto com Gordana Manic (pós-doc, IC-UNICAMP) e Laura Bahiense (Eng. Produção, COPPE-UFRJ).