The Study On The Edge Metric Dimension Problem Based On Variable Neighborhood Search Algorithms

The problem of edge metric dimension of a graph is one of the important problems in graph theory and combination optimization.This problem is presented in more and more areas,including network discovery and verification,robot navigation and chemistry.Let G=(V,E)be a simple graph.A vertex set B of G is called an edge metric generator for G if every two edges of G are distinguished by some vertex of B.An edge metric generator with the minimum cardinality is called an edge metric basis of G.The cardinality of an edge metric basis of G is called the edge metric dimension of G.The edge metric dimension problem is an NP-hard problem.In this thesis,we study the edge metric dimension problem,giving an integer linear programming model and designing a variable neighborhood search algorithm.We present the results of our variable neighborhood search algorithm applied to the Hamming graph,the hypercube graph and the Mobius Ladder graph.