Authors: Kratica, Jozef 
Kovačević-Vujčić, Vera
Čangalović, Mirjana
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Computing the metric dimension of graphs by genetic algorithms
Journal: Computational Optimization and Applications
Volume: 44
Issue: 2
First page: 343
Last page: 361
Issue Date: 1-Nov-2009
Rank: M21
ISSN: 0926-6003
DOI: 10.1007/s10589-007-9154-5
In this paper we consider the NP-hard problem of determining the metric dimension of graphs. We propose a genetic algorithm (GA) that uses the binary encoding and the standard genetic operators adapted to the problem. The feasibility is enforced by repairing the individuals. The overall performance of the GA implementation is improved by a caching technique. Since the metric dimension problem up to now has been considered only theoretically, standard test instances for this problem do not exist. For that reason, we present the results of the computational experience on several sets of test instances for other NP-hard problems: pseudo boolean, crew scheduling and graph coloring. Testing on instances with up to 1534 nodes shows that GA relatively quickly obtains approximate solutions. For smaller instances, GA solutions are compared with CPLEX results. We have also modified our implementation to handle theoretically challenging large-scale classes of hypercubes and Hamming graphs. In this case the presented approach reaches optimal or best known solutions for hypercubes up to 131072 nodes and Hamming graphs up to 4913 nodes.
Keywords: Evolutionary approach | Graph theory | Metric dimension
Publisher: Springer Link
Project: Serbian Ministry of Science, Grant No. 144015G

Show full item record


checked on Jun 22, 2024

Page view(s)

checked on May 10, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.