A column generation based algorithm for the robust graph coloring problem

DOI10.1016/j.dam.2016.09.006zbMath1359.05129OpenAlexW2521437826MaRDI QIDQ516837

Birol Yüceoğlu, Güvenç Şahin, Stan P. M. van Hoesel

Publication date: 15 March 2017

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

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

zbMATH Keywords

column generationreduced cost fixingrepresentatives formulationrobust graph coloringset-covering formulation

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (1)

New results on the robust coloring problem

Uses Software

• CALMA
• CPLEX
• Algorithm 457

Cites Work

• Fractional programming formulation for the vertex coloring problem
• A supernodal formulation of vertex colouring with applications in course timetabling
• Cliques, holes and the vertex coloring polytope
• A graph coloring algorithm for large scale scheduling problems
• The robust coloring problem.
• A branch-and-price algorithm for the robust graph coloring problem
• On the asymmetric representatives formulation for the vertex coloring problem
• A branch-and-cut algorithm for graph coloring
• Branch-and-Price: Column Generation for Solving Huge Integer Programs
• Maximizing Submodular Set Functions: Formulations and Analysis of Algorithms
• A Column Generation Approach for Graph Coloring
• Graph Colorings
• Reducibility among Combinatorial Problems
• AI 2003: Advances in Artificial Intelligence
• Algorithm 457: finding all cliques of an undirected graph
• Models and solution techniques for frequency assignment problems

This page was built for publication: A column generation based algorithm for the robust graph coloring problem