Exploramos o seguinte problema: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y sem símbolos repetidos. Estudamos a estrutura deste problema, particularmente do ponto de vista de grafos e de combinatória poliédrica. Desenvolvemos algoritmos de aproximação e heurísticas para este problema. O enfoque deste trabalho está na construção de um algoritmo baseado na técnica branch-and-cut, aproveitando-nos de um algoritmo de separação eficiente e de heurísticas e técnicas para encontrarmos uma solução ótima mais cedo. Também estudamos um problema mais fácil no qual este problema é baseado: dadas duas sequências X e Y sobre um alfabeto finito, encontre uma subsequência comum máxima de X e Y. Exploramos este problema do ponto de vista de combinatória poliédrica e descrevemos vários algoritmos conhecidos para resolvê-lo. / We explore the following problem: given two sequences X and Y over a finite alphabet, find a longest common subsequence of X and Y without repeated symbols. We study the structure of this problem, particularly from the point of view of graphs and polyhedral combinatorics. We develop approximation algorithms and heuristics for this problem. The focus of this work is in the construction of an algorithm based on the branch-and-cut technique, taking advantage of an efficient separation algorithm and of heuristics and techniques to find an optimal solution earlier. We also study an easier problem on which this problem is based: given two sequences X and Y over a finite alphabet, find a longest common subsequence of X and Y. We explore this problem from the point of view of polyhedral combinatorics and describe several known algorithms to solve it.

Sejam GI = (VI ,AI) e GM = (VM,AM) dois grafos simples. Um mapeamento de GI para GM é um conjunto de associações, tal que cada vértice de VI está associado a um vértice de VM, e cada aresta de AI está associada a um par de vértices de VM. A cada possível associação é atribuído um custo. O problema de correspondência inexata entre grafos (PCIG) consiste em encontrar um mapeamento de GI para GM, tal que a soma dos custos de suas associações seja mínima. Nesta dissertação, resumimos os resultados encontrados na literatura sobre o PCIG e algumas de suas variações. Os resultados que incluímos aqui tratam sobre a questão de como formular o PCIG e algumas de suas variações, através de programação linear inteira. Provamos alguns resultados de complexidade computacional que relacionam variações do PCIG a problemas clássicos, como isomorfismo e partição de grafos. Fornecemos uma formulação através de programação linear inteira para o PCCA (uma variante do PCIG com conexidade e cobertura de arestas). Mostramos que o PCCA é NP-difícil quando os grafos de entrada são completos ou árvores (chamamos o segundo caso de PCCA para árvores). Apresentamos uma formulação linear inteira e um algoritmo - que é polinomial se o grau máximo dos vértices de VM for limitado por uma constante - para o PCCA para árvores. Mostramos um caso especia em que o PCCA para árvores pode ser resolvido em tempo polinomial. Por último, exibimos alguns resultados experimentais, inclusive com instâncias reais de uma aplicação do problema. / 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.

Muitas relações min-max em otimização combinatória podem ser demonstradas através de total dual integralidade de sistemas lineares. O conceito algébrico de bases de Hilbert foi originalmente introduzido com o objetivo de melhor compreender a estrutura geral dos sistemas totalmente dual integrais. Resultados apresentados posteriormente mostraram que bases de Hilbert também são relevantes para a otimização combinatória em geral e para a caracterização de certas classes de objetos discretos. Entre tais resultados, foram provadas, a partir dessas bases, versões do teorema de Carathéodory para programação inteira. Nesta dissertação, estudamos aspectos estruturais e computacionais de bases de Hilbert e relações destas com programação inteira e otimização combinatória. Em particular, consideramos versões inteiras do teorema de Carathéodory e conjecturas relacionadas. / There are several min-max relations in combinatorial optimization that can be proved through total dual integrality of linear systems. The algebraic concept of Hilbert basis was originally introduced with the objective of better understanding the general structure of totally dual integral systems. Some results that were proved later have shown that Hilbert basis are also relevant to combinatorial optimization in a general manner and to characterize certain classes of discrete objects. Among such results, there are versions of Carathéodory\'s theorem for integer programming that were proved through those basis. In this dissertation, we study structural and computational aspects of Hilbert basis and their relations to integer programming and combinatorial optimization. In particular, we consider integer versions of Carathéodory\'s theorem and related conjectures.

Muitas relações min-max em otimização combinatória podem ser demonstradas através de total dual integralidade de sistemas lineares. O conceito algébrico de bases de Hilbert foi originalmente introduzido com o objetivo de melhor compreender a estrutura geral dos sistemas totalmente dual integrais. Resultados apresentados posteriormente mostraram que bases de Hilbert também são relevantes para a otimização combinatória em geral e para a caracterização de certas classes de objetos discretos. Entre tais resultados, foram provadas, a partir dessas bases, versões do teorema de Carathéodory para programação inteira. Nesta dissertação, estudamos aspectos estruturais e computacionais de bases de Hilbert e relações destas com programação inteira e otimização combinatória. Em particular, consideramos versões inteiras do teorema de Carathéodory e conjecturas relacionadas. / There are several min-max relations in combinatorial optimization that can be proved through total dual integrality of linear systems. The algebraic concept of Hilbert basis was originally introduced with the objective of better understanding the general structure of totally dual integral systems. Some results that were proved later have shown that Hilbert basis are also relevant to combinatorial optimization in a general manner and to characterize certain classes of discrete objects. Among such results, there are versions of Carathéodory\'s theorem for integer programming that were proved through those basis. In this dissertation, we study structural and computational aspects of Hilbert basis and their relations to integer programming and combinatorial optimization. In particular, we consider integer versions of Carathéodory\'s theorem and related conjectures.