On approximation algorithm for the edge metric dimension problem

Abstract In this paper, we study the edge metric dimension problem (EMDP). We establish a potential function and give a corresponding greedy algorithm with approximation ratio 1 + ln ⁡ n + ln ⁡ ( log 2 ⁡ n ) , where n is the number of vertices in the graph G.