Variable neighborhood search for the strong metric dimension problem

Abstract

We consider a variable neighborhood search approach for solving the strong metric dimension problem. The proposed method is based on the idea of decomposition and it is characterized by suitably chosen neighborhood structures and efficient local search. Computational experiments on ORLIB instances show that the new approach outperformes a genetic algorithm, the only existing heuristic in the literature for solving this problem.