An improved ant colony optimisation heuristic for graph colouring

DOI10.1016/J.DAM.2007.03.025MaRDI QIDQ2473031zbMATH OpenOpenAlexFDO

Authors K. Dowsland, J. Thompson

Publication date 26 February 2008

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2007.03.025

zbMATH Keywords

ant colony optimisationgraph colouringmeta-heuristic

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• An ACO algorithm for the graph coloring problem
• An ant colony algorithm for graph coloring and labeling problems
• Ant local search and its efficient adaptation to graph colouring
• An ant-based algorithm for coloring graphs
• scientific article; zbMATH DE number 1784918

Cites work

• A graph coloring algorithm for large scheduling problems
• A GRASP for coloring sparse graphs
• A procedure for the strategic planning of locations, capacities and districting of jails: application to Chile
• A variable neighborhood search for graph coloring.
• Ant colony optimization for the examination scheduling problem
• Ants can colour graphs
• Embedding a sequential procedure within an evolutionary algorithm for coloring problems in graphs
• Genetic algorithm for graph coloring: exploration of Galinier and Hao's algorithm
• Genetic and hybrid algorithms for graph coloring
• scientific article; zbMATH DE number 176480 (Why is no real title available?)
• scientific article; zbMATH DE number 2050708 (Why is no real title available?)
• scientific article; zbMATH DE number 2079895 (Why is no real title available?)
• scientific article; zbMATH DE number 956851 (Why is no real title available?)
• Hybrid evolutionary algorithms for graph coloring
• New methods to color the vertices of a graph
• Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
• Some experiments with simulated annealing for coloring graphs
• Using tabu search techniques for graph coloring

Cited in

(21)

• A general-purpose hill-climbing method for order independent minimum grouping problems: A case study in graph colouring and bin packing
• Strong valid inequalities for Boolean logical pattern generation
• A wide-ranging computational comparison of high-performance graph colouring algorithms
• A new ant colony optimization algorithm for the lower bound of sum coloring problem
• On the performance of scatter search for post-enrolment course timetabling problems
• Graph based twin cost matrices for unbalanced assignment problem with improved ant colony algorithm
• Simple decentralized graph coloring
• A new approach to the vertex coloring problem
• An ant algorithm for the partition graph coloring problem
• Informed reactive tabu search for graph coloring
• An ant colony algorithm for graph coloring and labeling problems
• Analysing the effects of solution space connectivity with an effective metaheuristic for the course timetabling problem
• Towards objective measures of algorithm performance across instance space
• An exact algorithm with learning for the graph coloring problem
• An ACO algorithm for the graph coloring problem
• Ant local search and its efficient adaptation to graph colouring
• Ants can colour graphs
• Online Optimization of a Color Sorting Assembly Buffer Using Ant Colony Optimization
• On the application of graph colouring techniques in round-robin sports scheduling
• Improving the extraction and expansion method for large graph coloring
• An improved hybrid ant-local search algorithm for the partition graph coloring problem

Describes a project that uses

Uses Software

• DIMACS

This page was built for publication: An improved ant colony optimisation heuristic for graph colouring

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