Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results
type: Item
instance of: scholarly article
title: Set covering and packing formulations of graph coloring: Algorithms and first polyhedral results
zbMATH Open document ID: 1279.90115
published in: Discrete Optimization
publication date: 2009-05-07T00:00:00Z
Mathematics Subject Classification ID: 90C09
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 90C57
zbMATH DE Number: 5552078
zbMATH Keywords: graph coloring
zbMATH Keywords: stable sets
zbMATH Keywords: facets
zbMATH Keywords: branch-cut-and-price algorithm
author: Pierre Hansen
author: Martine Labbé
author: David Schindl
MaRDI profile type: Publication
full work available at URL: j.disopt.2008.10.004
OpenAlex ID: W2004802557
cites work: On the set covering polytope. I: All the facets with coefficients in \(\{\) 0,1,2\(\}\)
cites work: \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts
cites work: Facets of the graph coloring polytope
cites work: Geometric algorithms and combinatorial optimization.
cites work: The fractional chromatic number of mycielski's graphs
cites work: A Column Generation Approach for Graph Coloring
cites work: Sur le coloriage des graphs
cites work: A polyhedral approach to edge coloring
cites work: On the facial structure of set packing polyhedra
cites work: On the facial structure of the set covering polytope
cites work: Q4382863
cites work: Combinatorial optimization. Polyhedra and efficiency (3 volumes)
DOI: 10.1016/J.DISOPT.2008.10.004
Recommended article: Constructions of optimal packing and covering of the complete multigraph with applications
Recommended article: Approximating k-set cover and complementary graph coloring
Recommended article: Q3829583
Recommended article: On packing and covering numbers of graphs
Recommended article: On packing \(S\)-colorings of subcubic graphs
Recommended article: Packing colorings of subcubic outerplanar graphs
Recommended article: A survey on packing colorings
Recommended article: Packing problems in edge-colored graphs
Recommended article: Covering Graphs by Colored Stable Sets
Recommended article: Packing coloring of generalized Sierpinski graphs
description: scientific article; zbMATH DE number 5552078