Dissertação

{en_GB=Solving treewidth in graphs using MaxSAT} {} EVALUATED

{pt=A treewidth eé uma propriedade de grafos que tem sido estudada ao longo de vários anos. Esta propriedade, permite-nos perceber o quão semelhante está um grafo de ser uma árvore (tree), quanto menor o valor da treewidth, mais próximo está o grafo original de ser uma árvore. Sabendo o valor de treewidth de um determinado grafo, e a correspondente decomposição em árvore, torna possível a redução de problemas conhecidamente NP-Hard. Isto significa que existem problemas em NP-Hard que podem ser resolvidos eficientemente através da aproximação do problema a uma decomposição em árvore com valor baixo para a treewidth. Apesar de ser sabido que uma decomposição em árvore de um determinado grafo, pode ser uma maneira de tornar eficiente a resolução de problemas em NP-Hard, arranjar o valor certo para a treewidth, bem como a correspondente decomposição em árvore, é por si só um problema NP-Hard. Neste documento, é apresentado e analisado parte do trabalho feito nesta área das ciências da computação, desde as relações entre a propriedade descrita com outras propriedades de grafos, passando por trabalho feito em algoritmos, na resolução e descoberta de métodos eficientes que permitam reconhecer a treewidth de grafos em tempo ou espaço útil. No fim de estudar algum deste trabalho feito sobre esta propriedade, é elaborada uma solução que visa resolver este problema recorrendo a lógica proposicional, mais precisamente, transformando o problema de encontrar a treewidth num problema de satisfação Booleana. Por último, são tirados e analisados os resultados obtidos com a solução proposta., en=Treewidth is an important property of graphs. Knowing the treewidth value for a given graph, and the corresponding optimal tree-decomposition, allows one to reduce and approximate well-known NP-Hard problems. This means that, there are NP-Hard problems which can be solved efficiently by approximating the problem instance to a tree-decomposition of small width. Despite the fact that knowing the treewidth value for graphs can be a solution for some NP-Hard problems, finding the treewidth value is an NP-Hard problem itself. In this document it is provided a survey on algorithms for solving the treewidth value of an arbitrary input graph with emphasis on the usage of SAT and MaxSAT formalizations. Moreover, it is also outlined a proposal to find the treewidth value of a graph, as well as the corresponding decomposition, using a MaxSAT based approach. Finally, the proposed solution is described, the evaluation the procedure is described, and the results are discussed.}
{pt=Treewidth, Decomposição em árvore, Ordenação Linear, Satisfação Máxima, en=Treewidth, Tree-Decomposition, Linear Ordering, Maximum Satisfiability}

Novembro 6, 2018, 16:30

Publicação

Obra sujeita a Direitos de Autor

Orientação

ORIENTADOR

Vasco Miguel Gomes Nunes Manquinho

Departamento de Engenharia Informática (DEI)

Professor Associado