The Study On The Mixed Metric Dimension Problem Based On Genetic Algorithms

The problems of the metric dimension,edge metric dimension and mixed metric dimension of graphs are important problems in graph theory and combinatorial opti-mization.They have been widely applied in the fields of monetary weighing,network discovery and validation,robot navigation,sonar and pharmaceutical chemistry.Let G=(V,E)be a graph and let S be a nonempty subset of V.S is called a mixed metric generator of G if any two elements(vertices or edges)in G can be distinguished by some vertex in S.The cardinality of the mixed metric generator with minimum cardinality is called the mixed metric dimension of G.In general,the mixed metric dimension problem is NP-hard problem.In this thesis,we design a genetic algorithm(GA)for solving the mixed metric dimension problem on simple connected graphs.We present the results of our genetic algorithm applied to the Hamming graph,the hypercube graph and the graph G?Pm.We indicate that the presented results reach their mixed metric dimension in some cases.