EPCOT: An efficient procedure for coloring optimally with Tabu Search

DOI10.1016/0898-1221(93)90279-5zbMath0798.68128OpenAlexW2053765750MaRDI QIDQ1802494

Dominique de Werra, Nicolas Dubois

Publication date: 31 October 1994

Published in: Computers \& Mathematics with Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0898-1221(93)90279-5

zbMATH Keywords

graph coloringrandom graphsNP-completeTabu Search

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Searching and sorting (68P10) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items (11)

A tabu search algorithm for computing an operational timetable ⋮ On the use of some known methods for \(T\)-colorings of graphs ⋮ Simulated annealing and tabu search in the long run: A comparison on QAP tasks ⋮ FITTING OF TABU SEARCH TO OPTIMIZE FUNCTIONS OF CONTINUOUS VARIABLES ⋮ Coloration de graphes : fondements et applications ⋮ Variants of simulated annealing for the examination timetabling problem ⋮ Metaheuristics: A bibliography ⋮ Embedding a sequential procedure within an evolutionary algorithm for coloring problems in graphs ⋮ A common Tabu search algorithm for the global optimization of engineering problems ⋮ A combined global and local search method to deal with constrained optimization for continuous tabu search ⋮ INFORMED REACTIVE TABU SEARCH FOR GRAPH COLORING

Uses Software

• Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Using tabu search techniques for graph coloring
• TABARIS: An exact algorithm based on tabu search for finding a maximum independent set in a graph
• Algorithms for the maximum satisfiability problem
• Tabu search techniques. A tutorial and an application to neural networks
• STABULUS: A technique for finding stable sets in large graphs with tabu search
• The tabu search metaheuristic: How we used it
• New methods to color the vertices of a graph
• Chromatic Scheduling and the Chromatic Number Problem

This page was built for publication: EPCOT: An efficient procedure for coloring optimally with Tabu Search