A branch-and-price algorithm for the robust graph coloring problem

DOI10.1016/J.DAM.2013.02.013MaRDI QIDQ2448920zbMATH OpenOpenAlexFDO

Authors Alain Hertz, C. Archetti, Nicola Bianchessi

Publication date 5 May 2014

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

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

zbMATH Keywords

branch-and-price algorithmgraph coloringrobust solutiontabu search

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85) Searching and sorting (68P10) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• A Branch-And-Price Approach for Graph Multi-Coloring
• A hybrid algorithm for the robust graph coloring problem
• A branch-and-price algorithm for the (k,c)-coloring problem
• A branch-and-price algorithm for the minimum sum coloring problem
• A branch-and-price approach for the partition coloring problem
• Solving the pricing problem in a branch-and-price algorithm for graph coloring using zero-suppressed binary decision diagrams
• Exact weighted vertex coloring via branch-and-price
• A Wide Branching Strategy for the Graph Coloring Problem
• Heuristics for the robust coloring problem

Cites work

• A Column Generation Approach for Graph Coloring
• AI 2003: Advances in Artificial Intelligence
• An adaptive memory algorithm for the k-coloring problem
• Branch-and-price: Column generation for solving huge integer programs
• Column Generation
• scientific article; zbMATH DE number 3356467 (Why is no real title available?)
• On the capacitated vehicle routing problem
• Solving the maximum clique problem using a tabu search approach
• STABULUS: A technique for finding stable sets in large graphs with tabu search
• The robust coloring problem.

Cited in

(19)

• The -connected assignment problem
• Accelerating the branch-and-price algorithm using machine learning
• The robust coloring problem.
• A branch and price algorithm for list coloring problem
• A matheuristic approach for the \(b\)-coloring problem using integer programming and a multi-start multi-greedy randomized metaheuristic
• A branch-and-price approach for the partition coloring problem
• Embedding a novel objective function in a two-phased local search for robust vertex coloring
• Solving the pricing problem in a branch-and-price algorithm for graph coloring using zero-suppressed binary decision diagrams
• A Wide Branching Strategy for the Graph Coloring Problem
• A hybrid algorithm for the robust graph coloring problem
• Soft graph coloring
• A Branch-And-Price Approach for Graph Multi-Coloring
• A branch-and-price algorithm for the (k,c)-coloring problem
• Three algorithms for graph locally harmonious colouring
• A column generation based algorithm for the robust graph coloring problem
• Heuristics for the robust coloring problem
• AI 2003: Advances in Artificial Intelligence
• New results on the robust coloring problem
• Solving the list coloring problem through a branch-and-price algorithm

This page was built for publication: A branch-and-price algorithm for the robust graph coloring problem

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