Implementação e análise de algoritmos para coloração de arestas
AUTOR(ES)
Tiago de Oliveira Januario
DATA DE PUBLICAÇÃO
2011
RESUMO
O problema de Coloração de Arestas, extensivamente estudado em Teoria dos Grafos, consiste em colorir as arestas de um grafo de tal forma que arestas incidentes em um mesmo vértice tenham cores distintas e que o número de cores utilizadas seja o menor possível. O resultado mais importante a respeito do problema de coloração de arestas surgiu em 1964 com o Teorema de Vizing, que definiu que o número mínimo de cores necessárias para colorir um grafo, denominado de índice cromático X, está limitado entre os valores quadrado e triangulo + 1, onde triangulo é o grau máximo do grafo. Neste trabalho são apresentados duas implementações eficientes para coloração de arestas de grafos simples, baseados no Teorema de Vizing, utilizando não mais que trinagulo + 1 cores. Várias adaptações em estruturas de dados e na ordem de processamento das arestas e cores foram propostas com o intuito de reduzir o tempo de execução das operações realizadas com maior frequência. Também foram desenvolvidas duas estratégias de pré-processamento que fornecem um grafo parcialmente colorido como entrada para o algoritmo de coloração de arestas. Os resultados experimentais mostram que as estratégias desenvolvidas permitem uma redução de 63,92% no tempo de execução das implementações dos algoritmos de coloração de arestas aqui estudados.
ASSUNTO(S)
computação teses. teoria dos grafos teses.
