DOI
10.11606/D.45.2008.tde-16092008-133830
Documento
Autor
Nome completo
Alexandre da Silva Freire
E-mail
Área do Conhecimento
Data de Defesa
Imprenta
São Paulo, 2008
Ferreira, Carlos Eduardo (Presidente)
Boeres, Maria Claudia Silva
Fernandes, Cristina Gomes
Título em português
Correspondência inexata entre grafos.
Palavras-chave em português
correspondência inexata entre grafos
otimização combinatória.
partição de grafos
programação inteira
programação linear
teoria dos grafos
Resumo em português
Título em inglês
inexact graph correspondence
Palavras-chave em inglês
combinatorial optimization.
graph partitioning
graph theory
inexact correspondence between graphs
integer programming
linear programming
Resumo em inglês
Let GI = (VI ,AI) and GM = (VM,AM) be two simple graphs. A mapping from GI to GM is an association set, such that each vertex in VI is associated to a vertex in VM, and each edge in AI is associated to a pair of vertices of VM. A cost is defined to each possible association. The inexact graph correspondence problem (IGCP) consists in finding a mapping from GI to GM, such that the sum of its associations costs is minimized. In this dissertation, we summarize the results found in the literature about the IGCP and some variations. The results included here address the question of how to formulate the IGCP and some variations, using integer linear programming. We prove some computational complexity results which relate IGCP variations with classical problems, like graph isomorphism and partitioning. We give an integer linear programming formulation to the ICEC (IGCP with connectivity and edges cover). We show that the ICEC is NP-hard when the input graphs are complete or trees (we call the second case ICEC for trees). We introduce an integer linear formulation and an algorithm - which has polynomial running time if the vertices of VM have maximum degree bounded by a constant - to the ICEC for trees. We show a especial case in which the ICEC for trees can be solved in polynomial time. Finally, we present some experimental results, also with instances of a real application of the problem.

AVISO - A consulta a este documento fica condicionada na aceitação das seguintes condições de uso:
Este trabalho é somente para uso privado de atividades de pesquisa e ensino. Não é autorizada sua reprodução para quaisquer fins lucrativos. Esta reserva de direitos abrange a todos os dados do documento bem como seu conteúdo. Na utilização ou citação de partes do documento é obrigatório mencionar nome da pessoa autora do trabalho.
Data de Publicação
2008-12-11

AVISO: Saiba o que são os trabalhos decorrentes clicando aqui.
Todos os direitos da tese/dissertação são de seus autores
Centro de Informática de São Carlos