Turbo-charging dominating set with an FPT subroutine: Further improvements and experimental analysis

Faisal N. Abu-Khzam, Shaowei Cai, Judith Egan, Peter Shaw, Kai Wang

    Research output: Contribution to journalArticlepeer-review


    Turbo-charging is a recent algorithmic technique that is based on the fixed-parameter tractability of the dynamic versions of some problems as a way to improve heuristics. We demonstrate the effectiveness of this technique and develop the turbo-charging idea further. A new hybrid heuristic for the Dominating Set problem that further improves this method is obtained by combining the turbo-charging technique with other standard heuristic tools including Local Search (LS). We implement both the recently proposed “turbo greedy” algorithm of Downey et al. [8] and a new method presented in this paper. The performance of these new heuristics is assessed on three suites of benchmark datasets, namely DIMACS, BHOSLIB and KONECT. Experiments comparing our algorithm to both heuristic and exact algorithms demonstrate its effectiveness. Our algorithm often produced results that were either exact or better than all the other available algorithms.
    Original languageEnglish
    Pages (from-to)59-70
    Number of pages12
    JournalLecture Notes in Computer Science
    Publication statusPublished - 1 Jan 2017
    EventConference on Theory and Applications of Models of Computation - Bern, Switzerland
    Duration: 20 Apr 201722 Apr 2017
    Conference number: 14th
    http://www.tamc2017.unibe.ch/ (Link to Conference Website)

    Cite this