- LAUR Home
- →
- School of Arts and Sciences
- →
- SoAS - Theses and Dissertations
- →
- View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.
| dc.contributor.author | Chahine, Bachir | |
| dc.date.accessioned | 2019-04-17T05:58:39Z | |
| dc.date.available | 2019-04-17T05:58:39Z | |
| dc.date.copyright | 2018 | en_US |
| dc.date.issued | 2019-04-17 | |
| dc.date.submitted | 2018-12-20 | |
| dc.identifier.uri | http://hdl.handle.net/10725/10466 | |
| dc.description.abstract | 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: | en_US |
| dc.language.iso | en | en_US |
| dc.subject | Lebanese American University -- Dissertations | en_US |
| dc.subject | Dissertations, Academic | en_US |
| dc.subject | Graph coloring | en_US |
| dc.subject | Turbogenerators -- Dynamics | en_US |
| dc.subject | Heuristic algorithms | en_US |
| dc.title | A dynamically turbo-charged heuristic for graph coloring. (c2018) | en_US |
| dc.type | Thesis | en_US |
| dc.term.submitted | Fall | en_US |
| dc.author.degree | MS in Computer Science | en_US |
| dc.author.school | SAS | en_US |
| dc.author.idnumber | 201605410 | en_US |
| dc.author.commembers | Haraty, Ramzi | |
| dc.author.commembers | Habre, Samer | |
| dc.author.department | Computer Science And Mathematics | en_US |
| dc.description.embargo | N/A | en_US |
| dc.description.physdesc | 1 hard copy: x, 35 leaves; ill.; 30 cm. available at RNL. | en_US |
| dc.author.advisor | Abu-Khzam, Faisal | |
| dc.keywords | Graph Coloring | en_US |
| dc.keywords | Parametrized Complexity | en_US |
| dc.keywords | Fixed Parameter Tractability | en_US |
| dc.keywords | Dynamic Problems | en_US |
| dc.keywords | Turbo-Charging | en_US |
| dc.description.bibliographiccitations | Bibliography: leaves 33-35. | en_US |
| dc.identifier.doi | https://doi.org/10.26756/th.2019.114 | en_US |
| dc.author.email | bachir.chahine@lau.edu | en_US |
| dc.identifier.tou | http://libraries.lau.edu.lb/research/laur/terms-of-use/thesis.php | en_US |
| dc.publisher.institution | Lebanese American University | en_US |
| dc.author.affiliation | Lebanese American University | en_US |
