A dynamically turbo-charged heuristic for graph coloring. (c2018)
We launch a study on the dynamic form of the graph coloring problem proving it to be fixed-parameter tractable with respect to the edit-parameter. This leads us to present a new turbo-charged heuristic for the problem that works by merging standard heuristic tools like Greedy coloring with the turbo...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| التنسيق: | masterThesis |
| منشور في: |
2018
|
| الموضوعات: | |
| الوصول للمادة أونلاين: | http://hdl.handle.net/10725/10466 https://doi.org/10.26756/th.2019.114 http://libraries.lau.edu.lb/research/laur/terms-of-use/thesis.php |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| الملخص: | We launch a study on the dynamic form of the graph coloring problem proving it to be fixed-parameter tractable with respect to the edit-parameter. This leads us to present a new turbo-charged heuristic for the problem that works by merging standard heuristic tools like Greedy coloring with the turbo-charging technique. The recently introduced turbo-charging idea is further enhanced in this thesis by introducing a dynamic version of turbo-charging where the moment of regret and the rollback points are determined dynamically. Experiments comparing our turbo-charging algorithm to other heuristics were conducted on a number of known benchmarks. Our heuristic produced exceptional results that were often better than all the other available heuristics. Keywords: |
|---|