Two Novel Evolutionary Formulations of the Graph Coloring Problem

Valmir C. Barbosa (), Carlos A.G. Assis and Josina O. Do Nascimento
Additional contact information
Valmir C. Barbosa: Universidade Federal do Rio de Janeiro
Carlos A.G. Assis: Universidade Federal do Rio de Janeiro
Josina O. Do Nascimento: Universidade Federal do Rio de Janeiro

Journal of Combinatorial Optimization, 2004, vol. 8, issue 1, No 4, 63 pages

Abstract: Abstract We introduce two novel evolutionary formulations of the problem of coloring the nodes of a graph. The first formulation is based on the relationship that exists between a graph's chromatic number and its acyclic orientations. It views such orientations as individuals and evolves them with the aid of evolutionary operators that are very heavily based on the structure of the graph and its acyclic orientations. The second formulation, unlike the first one, does not tackle one graph at a time, but rather aims at evolving a “program” to color all graphs belonging to a class whose members all have the same number of nodes and other common attributes. The heuristics that result from these formulations have been tested on some of the Second DIMACS Implementation Challenge benchmark graphs, and have been found to be competitive when compared to the several other heuristics that have also been tested on those graphs.

Keywords: graph coloring; evolutionary algorithms; genetic algorithms; genetic programming (search for similar items in EconPapers)
Date: 2004
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://link.springer.com/10.1023/B:JOCO.0000021937.26468.b2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:8:y:2004:i:1:d:10.1023_b:joco.0000021937.26468.b2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1023/B:JOCO.0000021937.26468.b2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().