EPCOT: An efficient procedure for coloring optimally with Tabu Search

DOI10.1016/0898-1221(93)90279-5MaRDI QIDQ1802494zbMATH OpenOpenAlexFDO

Authors 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 coloringNP-completerandom graphsTabu Search

Mathematics Subject Classification ID

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

Recommendations

• Tabu search with simple ejection chains for coloring graphs
• A tabu search heuristic for the equitable coloring problem
• A tabu search approach for the sum coloring problem
• scientific article; zbMATH DE number 597813
• Algoritmo de búsqueda tabú para una variante del problema de coloración
• Using tabu search techniques for graph coloring
• Informed reactive tabu search for graph coloring
• scientific article; zbMATH DE number 1488073

Cites work

• scientific article; zbMATH DE number 4152425 (Why is no real title available?)
• scientific article; zbMATH DE number 1062113 (Why is no real title available?)
• scientific article; zbMATH DE number 4187836 (Why is no real title available?)
• Algorithms for the maximum satisfiability problem
• Chromatic Scheduling and the Chromatic Number Problem
• New methods to color the vertices of a graph
• STABULUS: A technique for finding stable sets in large graphs with tabu search
• TABARIS: An exact algorithm based on tabu search for finding a maximum independent set in a graph
• Tabu search techniques. A tutorial and an application to neural networks
• The tabu search metaheuristic: How we used it
• Using tabu search techniques for graph coloring

Cited in

(14)

• A common Tabu search algorithm for the global optimization of engineering problems
• Embedding a sequential procedure within an evolutionary algorithm for coloring problems in graphs
• On the use of some known methods for \(T\)-colorings of graphs
• Metaheuristics: A bibliography
• Variants of simulated annealing for the examination timetabling problem
• On the greatest number of 2 and 3 colorings of a (v, e)-graph
• FITTING OF TABU SEARCH TO OPTIMIZE FUNCTIONS OF CONTINUOUS VARIABLES
• A tabu search algorithm for computing an operational timetable
• Simulated annealing and tabu search in the long run: A comparison on QAP tasks
• Using tabu search techniques for graph coloring
• A combined global and local search method to deal with constrained optimization for continuous tabu search
• Tabu search with simple ejection chains for coloring graphs
• Informed reactive tabu search for graph coloring
• Coloration de graphes : fondements et applications

Describes a project that uses

Uses Software

• TABARIS

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1802494)