Authors: Kratica, Jozef 
Čangalović, Mirjana
Kovačević-Vujčić, Vera
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Computing minimal doubly resolving sets of graphs
Journal: Computers and Operations Research
Volume: 36
Issue: 7
First page: 2149
Last page: 2159
Issue Date: 1-Jul-2009
Rank: M21a
ISSN: 0305-0548
DOI: 10.1016/j.cor.2008.08.002
In this paper we consider the minimal doubly resolving sets problem (MDRSP) of graphs. We prove that the problem is NP-hard and give its integer linear programming formulation. The problem is solved by a genetic algorithm (GA) that uses binary encoding and standard genetic operators adapted to the problem. Experimental results include three sets of ORLIB test instances: crew scheduling, pseudo-boolean and graph coloring. GA is also tested on theoretically challenging large-scale instances of hypercubes and Hamming graphs. Optimality of GA solutions on smaller size instances has been verified by total enumeration. For several larger instances optimality follows from the existing theoretical results. The GA results for MDRSP of hypercubes are used by a dynamic programming approach to obtain upper bounds for the metric dimension of large hypercubes up to 290 nodes, that cannot be directly handled by the computer.
Keywords: Evolutionary approach | Genetic algorithms | Hypercubes | Metric dimension | Minimal doubly resolving sets
Publisher: Elsevier
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.