A Metaheuristic Approach for the Vertex Coloring Problem

DOI10.1287/ijoc.1070.0245zbMath1243.90226OpenAlexW2060920237MaRDI QIDQ2901013

Paolo Toth, Enrico Malaguti, Michele Monaci

Publication date: 28 July 2012

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/ijoc.1070.0245

zbMATH Keywords

evolutionary algorithm set covering heuristics

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Learning and adaptive systems in artificial intelligence (68T05) Approximation methods and heuristics in mathematical programming (90C59) 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 (40)

Graph 3-coloring with a hybrid self-adaptive evolutionary algorithm ⋮ A memetic algorithm for the minimum sum coloring problem ⋮ An exact algorithm with learning for the graph coloring problem ⋮ Simple decentralized graph coloring ⋮ An exact algorithm for parallel machine scheduling with conflicts ⋮ A systematic study on meta-heuristic approaches for solving the graph coloring problem ⋮ A Wide Branching Strategy for the Graph Coloring Problem ⋮ Exact and approximate methods for the score-constrained packing problem ⋮ A massively parallel evolutionary algorithm for the partial Latin square extension problem ⋮ Heuristics for a project management problem with incompatibility and assignment costs ⋮ An exact approach for the vertex coloring problem ⋮ Quantum annealing of the graph coloring problem ⋮ A matrix approach to graph maximum stable set and coloring problems with application to multi-agent systems ⋮ Multi-coloring and job-scheduling with assignment and incompatibility costs ⋮ A graph coloring heuristic using partial solutions and a reactive tabu scheme ⋮ Graph Coloring Models and Metaheuristics for Packing Applications ⋮ A survey on vertex coloring problems ⋮ Variable space search for graph coloring ⋮ Hybrid evolutionary algorithm for the b-chromatic number ⋮ Optimization by ant algorithms: possible roles for an individual ant ⋮ Uncertain vertex coloring problem ⋮ Consistent neighborhood search for combinatorial optimization ⋮ A wide-ranging computational comparison of high-performance graph colouring algorithms ⋮ An evolutionary approach for bandwidth multicoloring problems ⋮ Coloring large graphs based on independent set extraction ⋮ An effective heuristic algorithm for sum coloring of graphs ⋮ A new \textsf{DSATUR}-based algorithm for exact vertex coloring ⋮ An evolutionary approach with diversity guarantee and well-informed grouping recombination for graph coloring ⋮ Improving the extraction and expansion method for large graph coloring ⋮ Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach ⋮ A metaheuristic framework for nonlinear capacitated covering problems ⋮ Solving the Pricing Problem in a Branch-and-Price Algorithm for Graph Coloring Using Zero-Suppressed Binary Decision Diagrams ⋮ A New Branch-and-Price-and-Cut Algorithm for One-Dimensional Bin-Packing Problems ⋮ The vertex coloring problem and its generalizations ⋮ Models and heuristic algorithms for a weighted vertex coloring problem ⋮ A search space ``cartography for guiding graph coloring heuristics ⋮ A memetic algorithm for graph coloring ⋮ A Generalized Consistent Neighborhood Search for Satellite Range Scheduling Problems ⋮ INFORMED REACTIVE TABU SEARCH FOR GRAPH COLORING ⋮ AN EXTRACTION AND EXPANSION APPROACH FOR GRAPH COLORING

Uses Software

DIMACS

This page was built for publication: A Metaheuristic Approach for the Vertex Coloring Problem