The metric dimension and related problems, computational experiences and some theoretical properties
Mirjana Cangalovic – University of Belgrade, Serbia
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.