dc.contributorSebastián Alberto Urrutia
dc.contributorAntonio Alfredo Ferreira Loureiro
dc.contributorGeraldo Robson Mateus
dc.creatorTiago de Oliveira Januario
dc.date.accessioned2019-08-14T04:42:42Z
dc.date.accessioned2022-10-03T23:50:52Z
dc.date.available2019-08-14T04:42:42Z
dc.date.available2022-10-03T23:50:52Z
dc.date.created2019-08-14T04:42:42Z
dc.date.issued2011-03-18
dc.identifierhttp://hdl.handle.net/1843/SLSS-8GQM36
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/3828948
dc.description.abstractThe Edge Coloring Problem, extensively studied in Graph Theory, concerns coloring the edges of a graph such that edges incident on the same vertex have distinct colors and the number of used colors is minimized. The most important result on the edge coloring problem was proposed in 1964 with Vizing's Theorem, which established that the minimum number of colors needed to color a graph, the chromatic index X, is limited between the values square and triangle + 1, where triangle is the maximum degree of the graph. This work presents two efficient edge coloring implementations for simple graphs based on Vizing's Theorem using no more than ? + 1 colors. Several adaptations in data structures and in the processing order of edges and colors have been proposed in order to reduce the runtime of the operations more frequently performed. We also developed two preprocessing strategies that provide a partially colored graph as input to the edge coloring algorithm. Experimental results show that the proposed strategies allow gains up to 63.92% in terms of performance in the edge coloring algorithms studied here.
dc.publisherUniversidade Federal de Minas Gerais
dc.publisherUFMG
dc.rightsAcesso Aberto
dc.subjectColoração de arestas
dc.subjectTeoria dos grafos
dc.subjectTeorema de Vizing
dc.subjectImplementações eficientes
dc.titleImplementação e análise de algoritmos para coloração de arestas
dc.typeDissertação de Mestrado


Este ítem pertenece a la siguiente institución