Algoritmos para super-coloração de vértices para grafos dirigidos

Abstract

Dado um grafo dirigido com os vértices coloridos, para cada vértice v, deseja-se saber qual o maior número de cores que os vértices de um caminho partindo de v podem ter. Diferentemente de problemas de coloração própria, para esse não há restrição de que vértices adjacentes tenham cores diferentes. Dentre as aplicações na literatura, há interesse na Antropologia para investigação sobre interação entre indivíduos de famílias e/ou clãs. A presente dissertação estuda, projeta e analisa métodos computacionais e suas propriedades para diversas versões conhecidas para o problema. Foram identificados algoritmos e propriedades para versões diferentes do problema, incluindo um algoritmo para grafos gerais, um algoritmo para 2 cores em grafos gerais, e algoritmos para 3 e k cores em DAGs. Um modelo de programação linear inteira também foi desenvolvido e implementado. Os algoritmos e os modelos foram executados usando tanto instâncias artificiais, quanto instâncias baseadas em redes genealógicas reais.

Abstract: Given a directed graph with colored vertices, we must know, for each vertex $v$, what is the maximum number of colors that a (simple) path starting at $v$ can reach. Unlike other classic problems, there is no restriction on the colors of adjacent vertices. Among different applications found in the literature, we are especially interested in an investigation in anthropology about interactions between individuals of certain families and/or kin. This project studies, designs, and analyzes computational methods and their properties for several known versions of the problem. Algorithms and properties for different versions of the problem were identified, including an algorithm for general graphs, an algorithm for 2 colors in general graphs, and algorithms for 3 and $k$ colors in DAGs. An integer linear programming model was also developed and implemented. The algorithms and models were executed using both artificial instances and instances based on real genealogical networks.