Titre : The Metric Dimension of Hypercubes

Conférencière : CANGALOVIC, Mijana (University of Belgrade, Serbie)

Résumé
The hypercube Qn of dimension n is the graph whose vertices are all n- dimensional binary vectors and where two vertices are adjacent if they differ only in one coordinate. Here we theoretically prove some symmetry properties of resolving sets in Qn and illustrate how they can be used to reduce the complexity of a procedure for finding the so called metric dimension β(Qn) of Qn, i.e. the minimal cardinality of a resolving set in Qn. Such a reduction is implemented within a simple constructive greedy heuristic which succeeded to find upper bounds of β(Qn) for higher values of dimension n, for which the existing VNS and GA algorithms, developed for an arbitrary graph, failed.