An exact algorithm with learning for the graph coloring problem

DOI10.1016/j.cor.2014.05.017zbMath1348.05207OpenAlexW1988588521MaRDI QIDQ337154

Ruchu Xu, Chong Huang, Zhaoyang Zhou, Chu-Min Li

Publication date: 10 November 2016

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2014.05.017

zbMATH Keywords

graph coloringbacktrackingSATclause learning

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) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (4)

Regular pattern-free coloring ⋮ A systematic study on meta-heuristic approaches for solving the graph coloring problem ⋮ Grouping products for the optimization of production processes: a case in the steel manufacturing industry ⋮ Constraint and Satisfiability Reasoning for Graph Coloring

Uses Software

• EXTRACOL
• DIMACS

Cites Work

• An exact approach for the vertex coloring problem
• Quantum annealing of the graph coloring problem
• An introduction to timetabling
• Graph colouring approaches for a satellite range scheduling problem
• A graph coloring model for a feasibility problem in monthly crew scheduling with preferential bidding
• A search space ``cartography for guiding graph coloring heuristics
• A memetic algorithm for graph coloring
• Improving heuristics for the frequency assignment problem
• On a graph-theoretical model for cyclic register allocation
• Coloration neighbourhood search with forward checking
• A wide-ranging computational comparison of high-performance graph colouring algorithms
• Coloring large graphs based on independent set extraction
• A new \textsf{DSATUR}-based algorithm for exact vertex coloring
• A graph-based hyper-heuristic for educational timetabling problems
• Generalised graph colouring by a hybrid of local search and constraint programming
• A cutting plane algorithm for graph coloring
• Coloring graphs by iterated local search traversing feasible and infeasible solutions
• Efficient algorithms for finding critical subgraphs
• An adaptive memory algorithm for the \(k\)-coloring problem
• An improved ant colony optimisation heuristic for graph colouring
• An exact method for graph coloring
• A survey of local search methods for graph coloring
• A branch-and-cut algorithm for graph coloring
• A Metaheuristic Approach for the Vertex Coloring Problem
• New methods to color the vertices of a graph
• A Column Generation Approach for Graph Coloring
• Finding the chromatic number by means of critical graphs

This page was built for publication: An exact algorithm with learning for the graph coloring problem