Results and open questions on the Metric Dimension problem
Speaker: Prof. Josep Diaz, Universitat Politecnica de Catalunya
Date: Wednesday, 11 December 2013
Time: 2:00PM
Location: Ashton Lecture Theatre, Ashton Building (#422 on University Campus map)
Host: Prof. Leszek Gasienic
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:
Maintained by Maintained by webmaster