Programação Genética para Colorir os Vértices de um Grafo

Autores

1968
Josina Oliveira do Nascimento
522,163
1969
Valmir Carneiro Barbosa
(Orientador)
522,163

Informações:

Publicações do PESC

Título
Programação Genética para Colorir os Vértices de um Grafo
Linha de pesquisa
Algoritmos e Combinatória
Tipo de publicação
Dissertação de Mestrado
Número de registro
Data da defesa
26/3/2001
Resumo
PESC: Resumo de Dissertação de Mestrado Resumo da Tese apresentada à COPPE/UFRJ como parte dos requisitos necessários para a obtenção do grau de Mestre em Ciências (M.Sc.)

Programação Genética para Colorir os Vértices de um Grafo

Josina Oliveira do Nascimento

Março/2001
Orientador: Valmir Carneiro Barbosa  

 
Programa: Engenharia de Sistemas e Computação

      Nessa tese foi desenvolvida a programação genética para coloração dos vértices de grafos. A idéia central é desenvolver programas que determinem a ordem de coloração dos vértices de acordo com seus graus. Cada programa é construído para um conjunto de grafos de mesmo número de vértices dentro de uma faixa de densidade de arestas. Programas assim obtidos colorem bem os grafos projetados para testar algoritmos de coloração de vértices e os resultados são comparáveis aos obtidos pelas heurísticas apresentadas no desafio DIMACS II em 1993.

Abstract
PESC: Master's Degree Abstract Abstract of Thesis presented at COPPE/UFRJ as a partial fulfillment of the requirements for the degree of Master of Science (M.Sc.)

Genetic Programming to Color the Vertices of a Graph

Josina Oliveira do Nascimento

March/2001
Advisor:Valmir Carneiro Barbosa  
Department: Systems Engineering and Computer Science

      This thesis is concerned with the development of genetic programming for graph coloring. The central idea is to evolve programs to colar vertices according to their degrees. Each program is built for a cla.gs of graphs having the same number of nades and edge density confined a certain intervalo The results programs do well on graph coloring testbeds and yield results comparable to those of the heuristics presented in the 1993 DIMACS Challenge.

Arquivo
Topo