Disertación de Maestría
DOI
10.11606/D.45.2008.tde-16092008-133830
Documento
Autor
Nombre completo
Alexandre da Silva Freire
Dirección Electrónica
Área de Conocimiento
Fecha de Defensa
Publicación
São Paulo, 2008
Director
Tribunal
Ferreira, Carlos Eduardo (Presidente)
Boeres, Maria Claudia Silva
Fernandes, Cristina Gomes
Título en portugués
Correspondência inexata entre grafos.
Palabras clave en portugués
correspondência inexata entre grafos
otimização combinatória.
partição de grafos
programação inteira
programação linear
teoria dos grafos
Resumen en portugués
Título en inglés
inexact graph correspondence
Palabras clave en inglés
combinatorial optimization.
graph partitioning
graph theory
inexact correspondence between graphs
integer programming
linear programming
Resumen en 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.

ADVERTENCIA - La consulta de este documento queda condicionada a la aceptación de las siguientes condiciones de uso:
Este documento es únicamente para usos privados enmarcados en actividades de investigación y docencia. No se autoriza su reproducción con finalidades de lucro. Esta reserva de derechos afecta tanto los datos del documento como a sus contenidos. En la utilización o cita de partes del documento es obligado indicar el nombre de la persona autora.
Fecha de Publicación
2008-12-11

ADVERTENCIA: Aprenda que son los trabajos derivados haciendo clic aquí.
Todos los derechos de la tesis/disertación pertenecen a los autores
Centro de Informática de São Carlos
Biblioteca Digital de Tesis y Disertaciones de la USP. Copyright © 2001-2021. Todos los derechos reservados.