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 | Abstract: | 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
SCOPUSTM
Citations
26
checked on Sep 7, 2024
Page view(s)
1
checked on Sep 7, 2024
Google ScholarTM
Check
Altmetric
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.