The Study On The Edge Metric Dimension Problem Based On Greedy Algorithms

The edge metric geneator and edge metric dimension are an important problem in the fields of graph theory and optimization.The edge metric dimension problem is an object proposed in recent years.Let G=(V,E)be a connected graph,the distance between the vertex w?V and the edge e=uv?E is defined as d(e,w)=min{d(u,w),d(v,w)}.A subset S is said to be an edge metric generator of G if every two distinct edges e1,e2 ? E and any vertex w?S,such that d(w,e1)?d(w,e2).In this thesis,we establish a potential function and present a corresponding greedy algorithm for the edge metric dimension problem.The main results are as follows.1.We construct a greedy algorithm to solve the edge metric dimension problem on the general graph.2.The greedy algorithm produces an approximate solution within a ratio(1+ln n)+ln(log2 n),where n is the number of vertices in the graph G.3.We give some results about the weight edge metric dimension on trees and cycles.