Variable neighborhood search for metric dimension and minimal doubly resolving set problems

Variable neighborhood search for metric dimension and minimal doubly resolving set problems

0.00 Avg rating0 Votes
Article ID: iaor20123253
Volume: 220
Issue: 2
Start Page Number: 328
End Page Number: 337
Publication Date: Jul 2012
Journal: European Journal of Operational Research
Authors: , , ,
Keywords: graphs, heuristics
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.

Reviews

Required fields are marked *. Your email address will not be published.