Groupe d’études et de recherche en analyse des décisions

The metric dimension and related problems, computational experiences and some theoretical properties

Mirjana Cangalovic University of Belgrade, Serbie

We consider two NP-hard problems on graphs: the metric dimension and the minimal doubly resolving set problems, and solve them by a GA-based heuristic approach. Numerical experiments are performed on various classes of graphs, including hypercubes, Hamming graphs and generalized Petersen graphs, as well as on crew scheduling and graph coloring ORLIB instances. In several cases the computational results indicate some theoretical properties which can be proved.