Results and open questions on the Metric Dimension problem

11^th December 2013, 14:00 Ashton Lecture Theatre
Professor Josep Diaz
Universitat Politecnica de Catalunya

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.

Additional Materials

• Slides