Symmetry properties of resolving sets and metric bases in hypercubes

Symmetry properties of resolving sets and metric bases in hypercubes

0.00 Avg rating0 Votes
Article ID: iaor20172919
Volume: 11
Issue: 6
Start Page Number: 1057
End Page Number: 1067
Publication Date: Aug 2017
Journal: Optimization Letters
Authors: , ,
Keywords: graphs, heuristics, combinatorial optimization, programming: dynamic
Abstract:

In this paper we consider some special characteristics of distances between vertices in the n equ1 ‐dimensional hypercube graph Q n equ2 and, as a consequence, the corresponding symmetry properties of its resolving sets. It is illustrated how these properties can be implemented within a simple greedy heuristic in order to find efficiently an upper bound of the so called metric dimension β ( Q n ) equ3 of Q n equ4 , i.e. the minimal cardinality of a resolving set in Q n equ5 . This heuristic was applied to generate upper bounds of β ( Q n ) equ6 for n equ7 up to 22 equ8 , which are for n 19 equ9 better than the existing ones. Starting from these new bounds, some existing upper bounds for 23 n 90 equ10 are improved by a dynamic programming procedure.

Reviews

Required fields are marked *. Your email address will not be published.