Exact weighted vertex coloring via branch-and-price

DOI10.1016/j.disopt.2012.03.002zbMath1246.90129OpenAlexW2070420791WikidataQ57659080 ScholiaQ57659080MaRDI QIDQ448972

Fabio Furini, Enrico Malaguti

Publication date: 11 September 2012

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

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

zbMATH Keywords

column generationcomputational experimentsvertex coloringbranch-and-price

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15)

Related Items (7)

An exact algorithm for the partition coloring problem ⋮ On Monte Carlo tree search for weighted vertex coloring ⋮ Iterated local search with tabu search for the weighted vertex coloring problem ⋮ Graph coloring-based approach for railway station design analysis and capacity determination ⋮ Adaptive feasible and infeasible tabu search for weighted vertex coloring ⋮ Solving vertex coloring problems as maximum weight stable set problems ⋮ Interval scheduling with economies of scale

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• An exact approach for the vertex coloring problem
• Time slot scheduling of compatible jobs
• The vertex coloring problem and its generalizations
• Models and heuristic algorithms for a weighted vertex coloring problem
• Weighted coloring: further complexity and approximability results
• An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment
• A survey on vertex coloring problems
• Safe Lower Bounds for Graph Coloring
• A Column Generation Approach for Graph Coloring
• Reactive GRASP: An Application to a Matrix Decomposition Problem in TDMA Traffic Assignment
• A Heuristic Method for the Set Covering Problem

This page was built for publication: Exact weighted vertex coloring via branch-and-price