An exact algorithm for the partition coloring problem

DOI10.1016/j.cor.2017.12.019zbMath1391.90603OpenAlexW2778024817MaRDI QIDQ1651600

Fabio Furini, Enrico Malaguti, Alberto Santini

Publication date: 12 July 2018

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

Full work available at URL: https://basepub.dauphine.fr/handle/123456789/18641

zbMATH Keywords

column generationvertex coloringbranch-and-price algorithmpartitioning coloringselective coloring

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

An Image-Based Approach to Detecting Structural Similarity Among Mixed Integer Programs, An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs, A note on selective line-graphs and partition colorings, Interval scheduling with economies of scale

Uses Software

• irace
• sgcp-via-cliques
• gCol

Cites Work

• Unnamed Item
• Unnamed Item
• On the minimum and maximum selective graph coloring problems in some graph classes
• An exact approach for the vertex coloring problem
• Exact weighted vertex coloring via branch-and-price
• Solving vertex coloring problems as maximum weight stable set problems
• Branching in branch-and-price: A generic scheme
• Routing and wavelength assignment by partition colouring
• Cliques, holes and the vertex coloring polytope
• Perfectness of clustered graphs
• Maximum-weight stable sets and safe lower bounds for graph coloring
• A branch-and-price approach for the partition coloring problem
• On the complexity of the selective graph coloring problem in some special classes of graphs
• On the asymmetric representatives formulation for the vertex coloring problem
• Automatic Dantzig-Wolfe reformulation of mixed integer programs
• On some applications of the selective graph coloring problem
• Branch-and-Price: Column Generation for Solving Huge Integer Programs
• Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation
• A survey on vertex coloring problems
• Partial Convexification of General MIPs by Dantzig-Wolfe Reformulation
• A branch-and-cut algorithm for partition coloring
• A Column Generation Approach for Graph Coloring
• Column Generation
• gCol