inexact graph correspondence / Correspondência inexata entre grafos.
AUTOR(ES)
Alexandre da Silva Freire
DATA DE PUBLICAÇÃO
2008
RESUMO
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.
ASSUNTO(S)
correspondência inexata entre grafos graph theory inexact correspondence between graphs otimização combinatória. teoria dos grafos combinatorial optimization. programação inteira integer programming linear programming programação linear partição de grafos graph partitioning
