2018/12/29 by Faisal N. Abu-Khzam, Abu-Khzam, Faisal N., Bachir M. Chahine +1
Computer Science · Decision Sciences · Engineering · #Advanced Graph Theory Research #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Scheduling and Timetabling Solutions #Vehicle Routing Optimization Methods
paper · pdf · doi:10.48550/arxiv.1812.11254
openalex publication_date 2018/12/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce a dynamic version of the graph coloring problem and prove its fixed-parameter tractability with respect to the edit-parameter. This is used to present a \em turbo-charged heuristic for the problem that works by combining the turbo-charging technique with other standard heuristic tools, including greedy coloring. The recently introduced turbo-charging idea is further enhanced in this paper by introducing a dynamic version of the so called \em moment of regret and \em rollback points. Experiments comparing our turbo-charging algorithm to other heuristics demonstrate its effectiveness. Our algorithm often produced results that were either exact or better than all the other available heuristics.