Authors: Mladenović, Nenad 
Kratica, Jozef 
Kovačević-Vujčić, Vera
Čangalović, Mirjana
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Variable neighborhood search for metric dimension and minimal doubly resolving set problems
Journal: European Journal of Operational Research
Volume: 220
Issue: 2
First page: 328
Last page: 337
Issue Date: 16-Jul-2012
Rank: M21a
ISSN: 0377-2217
DOI: 10.1016/j.ejor.2012.02.019
In this paper, two similar NP-hard optimization problems on graphs are considered: the metric dimension problem and the problem of determining a doubly resolving set with the minimum cardinality. Both are present in many diverse areas, including network discovery and verification, robot navigation, and chemistry. For each problem, a new mathematical programming formulation is proposed. For solving more realistic large-size instances, a variable neighborhood search based heuristic is designed. An extensive experimental comparison on five different types of instances indicates that the VNS approach consistently outperforms a genetic algorithm, the only existing heuristic in the literature designed for solving those problems.
Keywords: Combinatorial optimization | Metaheuristics | Metric dimension | Minimal doubly resolving set | Variable neighborhood search
Publisher: Elsevier
Project: Mathematical Modelas and Optimization Methods on Large-Scale Systems 
Graph theory and mathematical programming with applications in chemistry and computer science 

Show full item record


checked on Jun 11, 2024

Page view(s)

checked on May 10, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.