✦ LIBER ✦
Epcot: An efficient procedure for coloring optimally with Tabu Search
✍ Scribed by N. Dubois; D. de Werra
- Publisher
- Elsevier Science
- Year
- 1993
- Tongue
- English
- Weight
- 707 KB
- Volume
- 25
- Category
- Article
- ISSN
- 0898-1221
No coin nor oath required. For personal study only.
✦ Synopsis
We present an exact procedure for coloring the nodes of s graph with as few colors as possible. The problem o~ deciding whether an arbitrary graph can be colored with k colars is NP-complete. The procedure is based ms an implicit enumm'&tion technique. At some stsgrs of the algorithm heuristic methods are needed; here we will use the Tabu Search technique. The resulting coloring procedure is described. Computational experience is reported; it shows that random graphs with edge density 0.5 and having up to 70 nodes can be colored in an optimum way.