Kratica, Jozef; Kovačević-Vujčić, Vera; Čangalović, Mirjana Computing strong metric dimension of some special classes of graphs by genetic algorithms. (English) Zbl 1199.68546 Yugosl. J. Oper. Res. 18, No. 2, 143-151 (2008). 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. Reviewer: Tatjana Davidović (Beograd) Cited in 11 Documents MSC: 68W20 Randomized algorithms 90C27 Combinatorial optimization Keywords:graph invariant; stochastic algorithms; evolutionary computing; heuristic search PDFBibTeX XMLCite \textit{J. Kratica} et al., Yugosl. J. Oper. Res. 18, No. 2, 143--151 (2008; Zbl 1199.68546) Full Text: DOI