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

DOI10.1016/J.ORL.2011.02.006MaRDI QIDQ2275580zbMATH OpenOpenAlexFDO

Authors Edna A. Hoshino, Y. Frota, 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

branch-and-price algorithmcolumn generationgraph coloringinteger programming

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Integer programming (90C10)

Recommendations

• A branch-and-cut algorithm for partition coloring
• An exact algorithm for the partition coloring problem
• A Branch-And-Price Approach for Graph Multi-Coloring
• A branch-and-price algorithm for the robust graph coloring problem
• A branch-and-price algorithm for the minimum sum coloring problem

Cites work

• A branch-and-cut algorithm for partition coloring
• A Column Generation Approach for Graph Coloring
• A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing
• Cliques, holes and the vertex coloring polytope
• Finding a Maximum Clique in an Arbitrary Graph
• scientific article; zbMATH DE number 5158521 (Why is no real title available?)
• scientific article; zbMATH DE number 3356467 (Why is no real title available?)
• Routing and wavelength assignment by partition colouring
• Vertex packings: Structural properties and algorithms

Cited in

(17)

• Properties of some ILP formulations of a class of partitioning problems
• An exact algorithm for the partition coloring problem
• Perfectness of clustered graphs
• An exact cutting plane algorithm to solve the selective graph coloring problem in perfect graphs
• A branch and price algorithm for list coloring problem
• A note on selective line-graphs and partition colorings
• A branch-and-price algorithm for the robust graph coloring problem
• On some applications of the selective graph coloring problem
• On the minimum and maximum selective graph coloring problems in some graph classes
• Solving the pricing problem in a branch-and-price algorithm for graph coloring using zero-suppressed binary decision diagrams
• A branch-and-cut algorithm for partition coloring
• A Branch-And-Price Approach for Graph Multi-Coloring
• A branch-and-price algorithm for the (k,c)-coloring problem
• A set packing model for the partition coloring problem
• An improved hybrid ant-local search algorithm for the partition graph coloring problem
• Routing and wavelength assignment by partition colouring
• Solving a multicoloring problem with overlaps using integer programming

This page was built for publication: A branch-and-price approach for the partition coloring problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2275580)