The Study On The Mixed Metric Dimension Problem Based On Variable Neighberhood Search Algorithms

Let G=(V,E)be a graph.A vertex v is said to distinguish two elements(vertices and edges)x,y of G if d(x,v)? d(y,v),where d(x,v),d(y,v)represent the distance between the element x,y and the vertex v respectively.A subset W of the vertex set V is a mixed metric generator if any two distinct elements(vertices or edges)of G are distinguished by some vertex v E W.The cardinality of the mixed metric generator with the least elements is called the mixed metric dimension of G.The problem of mixed metric dimension is an important problem in graph theory and combinatorial optimization.Determining the mixed metric dimension of a graph is an NP-hard problem,so for large-scale mixed metric dimension problems,we need to consider its effective algorithm.In this thesis,we present two linear programming models,design the variable neighborhood search algorithm and apply this algorithm to some graphs to get bounds for their mixed metric dimension.