Models and heuristic algorithms for a weighted vertex coloring problem

DOI10.1007/s10732-008-9075-1zbMath1189.90180OpenAlexW2090980693MaRDI QIDQ1038841

Paolo Toth, Michele Monaci, Enrico Malaguti

Publication date: 20 November 2009

Published in: Journal of Heuristics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10732-008-9075-1

zbMATH Keywords

computational experimentsvertex coloringmathematical modelstraffic matrix decomposition

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Approximation methods and heuristics in mathematical programming (90C59) Coloring of graphs and hypergraphs (05C15)

Related Items

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 ⋮ Monte Carlo tree search with adaptive simulation: a case study on weighted vertex coloring ⋮ Adaptive feasible and infeasible tabu search for weighted vertex coloring ⋮ Exact weighted vertex coloring via branch-and-price ⋮ Solving vertex coloring problems as maximum weight stable set problems ⋮ A branch and price algorithm to solve the integrated production planning and scheduling in bulk ports ⋮ A metaheuristic framework for nonlinear capacitated covering problems ⋮ A one-to-one correspondence between colorings and stable sets ⋮ Exact Algorithms for Weighted Coloring in Special Classes of Tree and Cactus Graphs ⋮ The vertex coloring problem and its generalizations

Uses Software

• DIMACS

Cites Work

• Unnamed Item
• Unnamed Item
• Time slot scheduling of compatible jobs
• Weighted coloring: further complexity and approximability results
• Approximation algorithms for combinatorial problems
• An optimal column-generation-with-ranking algorithm for very large scale set partitioning problems in traffic assignment
• Models and bounds for two-dimensional level packing problems
• Batch processing with interval graph compatibilities between tasks
• A Set-Covering-Based Heuristic Approach for Bin-Packing Problems
• A Metaheuristic Approach for the Vertex Coloring Problem
• A Linear Programming Approach to the Cutting-Stock Problem
• Optimization by Simulated Annealing: An Experimental Evaluation; Part II, Graph Coloring and Number Partitioning
• New methods to color the vertices of a graph
• A Column Generation Approach for Graph Coloring
• Scheduling Semiconductor Burn-In Operations to Minimize Total Flowtime
• Reactive GRASP: An Application to a Matrix Decomposition Problem in TDMA Traffic Assignment
• A Heuristic Method for the Set Covering Problem
• A Linear Programming Approach to the Cutting Stock Problem—Part II