×

Computing strong metric dimension of some special classes of graphs by genetic algorithms. (English) Zbl 1199.68546

The NP-hard problem of determining an invariant of a graph called strong metric dimension (sdim) is solved by a genetic algorithm. The proposed algorithm uses binary representation of the solutions, mutation with the frozen genes, a limited number of different individuals with the same value of the strong metric dimension and a caching technique. Infeasible individuals are not rejected but corrected in order to assure their feasibility. The checking of feasibility and reparation of infeasible individuals represent main complexity of the algorithm. Procedure for checking the feasibility of a solution has complexity \(O(n^2\operatorname{sdim}(G))\) where \(n\) denotes the number of vertices. Experimental evaluation is performed on two special classes of ORLIB examples: crew scheduling and graph coloring.

MSC:

68W20 Randomized algorithms
90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI