A branch-and-price approach for the partition coloring problem

DOI10.1016/j.orl.2011.02.006zbMath1218.90127MaRDI QIDQ2275580

Yuri Frota, Edna A. Hoshino, Cid Carvalho De Souza

Publication date: 9 August 2011

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.orl.2011.02.006

zbMATH Keywords

integer programming; column generation; graph coloring; branch-and-price algorithm

Mathematics Subject Classification ID

90C10: Integer programming

05C15: Coloring of graphs and hypergraphs

Related Items

On the minimum and maximum selective graph coloring problems in some graph classes, An improved hybrid ant-local search algorithm for the partition graph coloring problem, An exact algorithm for the partition coloring problem, Perfectness of clustered graphs, A note on selective line-graphs and partition colorings, On some applications of the selective graph coloring problem

Cites Work

• Unnamed Item
• Unnamed Item
• Routing and wavelength assignment by partition colouring
• Cliques, holes and the vertex coloring polytope
• A branch-and-cut algorithm for partition coloring
• Finding a Maximum Clique in an Arbitrary Graph
• A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
• Vertex packings: Structural properties and algorithms
• A Column Generation Approach for Graph Coloring