Exact weighted vertex coloring via branch-and-price

DOI10.1016/J.DISOPT.2012.03.002MaRDI QIDQ448972zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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

computational experimentscolumn generationbranch-and-pricevertex coloring

Mathematics Subject Classification ID

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

Recommendations

• Models and heuristic algorithms for a weighted vertex coloring problem
• An exact approach for the vertex coloring problem
• Iterated local search with tabu search for the weighted vertex coloring problem
• Solving the minimum-weighted coloring problem
• Exact Algorithms for Weighted Coloring in Special Classes of Tree and Cactus Graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3050594 (Why is no real title available?)
• A Column Generation Approach for Graph Coloring
• A Heuristic Method for the Set Covering Problem
• A survey on vertex coloring problems
• An exact approach for the vertex coloring problem
• An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment
• Models and heuristic algorithms for a weighted vertex coloring problem
• Reactive GRASP: An Application to a Matrix Decomposition Problem in TDMA Traffic Assignment
• Safe lower bounds for graph coloring
• Scheduling on a batch machine with job compatibilities
• The vertex coloring problem and its generalizations
• Time slot scheduling of compatible jobs
• Weighted coloring: further complexity and approximability results

Cited in

(15)

• Interval scheduling with economies of scale
• On Monte Carlo tree search for weighted vertex coloring
• An exact approach for the vertex coloring problem
• Conflict optimization for binary CSP applied to minimum partition into plane subgraphs and graph coloring
• Minimum partition into plane subgraphs: the CG:SHOP challenge 2022
• Solving the list coloring problem through a branch-and-price algorithm
• A branch-and-price algorithm for the robust graph coloring problem
• Solving vertex coloring problems as maximum weight stable set problems
• Adaptive feasible and infeasible tabu search for weighted vertex coloring
• An exact algorithm for the partition coloring problem
• Models and heuristic algorithms for a weighted vertex coloring problem
• Exact Algorithms for Weighted Coloring in Special Classes of Tree and Cactus Graphs
• Solving the pricing problem in a branch-and-price algorithm for graph coloring using zero-suppressed binary decision diagrams
• Iterated local search with tabu search for the weighted vertex coloring problem
• Graph coloring-based approach for railway station design analysis and capacity determination

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

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