On approximation algorithm for the edge metric dimension problem

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.

Authors

• Yufei Huang Westlake University
• Bo Hou
• Wen Liu
• Lidong Wu
• Stephen Rainwater
• Suogang Gao

Keywords

• Edge metric generator
• Edge metric dimension
• Approximation algorithms
• Submodular function