Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results

DOI10.1016/j.disopt.2008.10.004zbMath1279.90115OpenAlexW2004802557MaRDI QIDQ1015318

Martine Labbé, Pierre Hansen, David Schindl

Publication date: 7 May 2009

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2008.10.004

zbMATH Keywords

graph coloringstable setsfacetsbranch-cut-and-price algorithm

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Linear programming (90C05) Boolean programming (90C09) Coloring of graphs and hypergraphs (05C15)

Related Items

A polyhedral study of the maximum stable set problem with weights on vertex-subsets, Branch-and-Cut-and-Price algorithms for the preemptive RCPSP, A hybrid K-means and integer programming method for commercial territory design: a case study in meat distribution, Facet-inducing web and antiweb inequalities for the graph coloring polytope, An integer programming approach to b-coloring, Exploring the role of graph spectra in graph coloring algorithm performance, Geodesic packing in graphs, Improved handling of uncertainty and robustness in set covering problems, Maximum-weight stable sets and safe lower bounds for graph coloring, An exact approach for the vertex coloring problem, The maximum-impact coloring polytope, A survey on vertex coloring problems, A branch-and-price algorithm for the minimum sum coloring problem, A new \textsf{DSATUR}-based algorithm for exact vertex coloring, Combining lithography and directed self assembly for the manufacturing of vias: connections to graph coloring problems, integer programming formulations, and numerical experiments, Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation

Cites Work

• Unnamed Item
• On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\)
• On the facial structure of the set covering polytope
• A polyhedral approach to edge coloring
• Geometric algorithms and combinatorial optimization.
• \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Facets of the graph coloring polytope
• A Column Generation Approach for Graph Coloring
• The fractional chromatic number of mycielski's graphs
• On the facial structure of set packing polyhedra
• Sur le coloriage des graphs