Results and open questions on the Metric Dimension problem

11^th December 2013, 14:00 Ashton Lecture Theater
Prof Josep Diaz
Departament de Llenguatges i Sistemes Informatics
Universitat Politecnica de Catalunya
Barcelona, Spain

Abstract

In this talk we will survey some recent results on the Metric Dimension problem. The problem
was posed by Harary and Slater in the 70's and until recently there were few complexity results,
other than it being NPC for general graphs and P for some specific families of graphs.
In the first part of the talk, we present recent advances in studying the complexity of Metric
Dimension and pose some open questions. In the second part, we present some results about
the expected value of metric dimension for different families of random graphs.