Hybrid evolutionary search for the minimum sum coloring problem of graphs

DOI10.1016/j.ins.2016.02.051zbMath1398.68494OpenAlexW2289330054MaRDI QIDQ1615675

Yan Jin, Jin-Kao Hao

Publication date: 31 October 2018

Published in: Information Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ins.2016.02.051

zbMATH Keywords

tabu searchlocal optimizationsum coloringevolutionary computinghybrid search

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Minimum sum coloring problem: upper bounds for the chromatic strength ⋮ Responsive threshold search based memetic algorithm for balanced minimum sum-of-squares clustering ⋮ Adaptive feasible and infeasible tabu search for weighted vertex coloring ⋮ A branch-and-price algorithm for the minimum sum coloring problem ⋮ ILP models and column generation for the minimum sum coloring problem ⋮ Computing lower bounds for minimum sum coloring and optimum cost chromatic partition ⋮ Combining CP and ILP in a tree decomposition of bounded height for the sum colouring problem ⋮ An efficient local search framework for the minimum weighted vertex cover problem

Uses Software

• Scatter Search
• Tabu search

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A memetic algorithm for the minimum sum coloring problem
• Using tabu search techniques for graph coloring
• Minimum sum set coloring of trees and line graphs of trees
• An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring
• A memetic algorithm for graph coloring
• Tabu search for nonlinear and parametric optimization (with links to genetic algorithms)
• An effective heuristic algorithm for sum coloring of graphs
• On sum coloring of graphs
• Genetic and hybrid algorithms for graph coloring
• Hybrid evolutionary algorithms for graph coloring
• \(\text{MA}\mid\text{PM}\): memetic algorithms with population management
• Lower Bounds for the Minimal Sum Coloring Problem
• A graph coloring algorithm for large scheduling problems
• New methods to color the vertices of a graph
• Minimum Color Sum of Bipartite Graphs
• A Gentle Introduction to Memetic Algorithms
• Graph Colorings
• Approximation Results for the Optimum Cost Chromatic Partition Problem
• Solving Scheduling Problems by Evolutionary Algorithms for Graph Coloring Problem