Fault-tolerant Metric Dimension Problem: A New Integer Linear Programming Formulation and Exact Formula for Grid Graphs

Ana Simić, Milena Bogdanović, Zoran Maksimović, Jelisavka Milošević

In this paper, fault-tolerant metric dimension problem (FTMDP) is considered. The existing integer linear programing (ILP) formulation, from the literature is improved, using lesser number of variables and constraints. Correctness proof shows that improved linear programing formulation is equivalent to the existing one. Computational results on random graphs proposed for similar problems in the literature, clearly show the advantage of a new ILP formulation. Additionally, the exact value of fault-tolerant metric dimension of grid graphs are given and proved.