Reformulação do Problema de Isomorfismo de Grafos Como Problema Quadrático de Alocação
Nome: LUCIANA LEE
Tipo: Dissertação de mestrado acadêmico
Data de publicação: 10/09/2007
Orientador:
Nome |
Papel |
|---|---|
| MARIA CLAUDIA SILVA BOERES | Co-orientador |
Banca:
| Nome |
Papel |
|---|---|
| ARLINDO GOMES DE ALVARENGA | Examinador Interno |
| MARIA CLAUDIA SILVA BOERES | Coorientador |
| MARIA CRISTINA RANGEL | Orientador |
| NAIR MARIA MAIA DE ABREU | Examinador Externo |
Resumo: Neste trabalho apresentamos uma reformulação do Problema de Isomor smo de Grafos
(PIG) como um Problema Quadrático de Alocação (PQA). Analisamos as vantagens
da aplicação das características do PIG para resolver o problema reformulado. Validamos
a reformulação através de um teorema e propomos a adaptação de três algoritmos,
sendo dois baseados em meta-heurísticas e um algoritmo de backtracking. Finalmente,
apresentamos os resultados computacionais da aplicação dos três algoritmos ao problema
reformulado.
