A comparison of integer programming models for the partial directed weighted improper coloring problem

DOI10.1016/j.dam.2018.08.026zbMath1410.05077OpenAlexW2897824369MaRDI QIDQ2414468

François Gagnon, Romain Montagné, Alain Hertz

Publication date: 17 May 2019

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

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

zbMATH Keywords

integer programmingvalid inequalitiesbranch-and-cutbranch-and-priceweighted improper vertex coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20) Signed and weighted graphs (05C22)

Uses Software

• DipPy
• DIP

Cites Work

• Unnamed Item
• Directed weighted improper coloring for cellular channel allocation
• Separation algorithms for 0-1 knapsack polytopes
• Branch-and-Price: Column Generation for Solving Huge Integer Programs
• Constructive algorithms for the partial directed weighted improper coloring problem
• Column Generation based Primal Heuristics
• Weighted Improper Colouring
• A graph coloring algorithm for large scheduling problems
• New methods to color the vertices of a graph
• On the Shannon capacity of a graph
• A Column Generation Approach for Graph Coloring