Two novel evolutionary formulations of the graph coloring problem

Details Two novel evolutionary formulations of the graph coloring problem Two novel evolutionary formulations of the graph coloring problem

2003-09-23

arxiv.org/abs/cs/0309039v1

Journal of Combinatorial Optimization 8 (2004), 41-63

Computer Science

Neural and Evolutionary Computing

To appear in Journal of Combinatorial Optimization

Scientific paper

10.1023/B:JOCO.0000021937.26468.

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.

Affiliated with

Also associated with

No associations

Rating

Two novel evolutionary formulations of the graph coloring problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Two novel evolutionary formulations of the graph coloring problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two novel evolutionary formulations of the graph coloring problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-182668