Geodesic
Fault-tolerant Metric Dimension Problem: A New Integer Linear Programming Formulation and Exact Formula for Grid Graphs
Kragujevac Journal of Mathematics, Tome 42 (2018) no. 4, p. 495 .

Voir la notice de l'article provenant de la source eLibrary of Mathematical Institute of the Serbian Academy of Sciences and Arts

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.
Classification : 90C10 05C12, 68R10
Keywords: Integer linear programming, fault-tolerant metric dimension 
@article{KJM_2018_42_4_a1,
     author = {Ana Simi\'c and Milena Bogdanovi\'c and Zoran Maksimovi\'c and Jelisavka Milo\v{s}evi\'c},
     title = {Fault-tolerant {Metric} {Dimension} {Problem:} {A} {New} {Integer} {Linear} {Programming} {Formulation} and {Exact} {Formula} for {Grid} {Graphs}},
     journal = {Kragujevac Journal of Mathematics},
     pages = {495 },
     publisher = {mathdoc},
     volume = {42},
     number = {4},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KJM_2018_42_4_a1/}
}
TY  - JOUR
AU  - Ana Simić
AU  - Milena Bogdanović
AU  - Zoran Maksimović
AU  - Jelisavka Milošević
TI  - Fault-tolerant Metric Dimension Problem: A New Integer Linear Programming Formulation and Exact Formula for Grid Graphs
JO  - Kragujevac Journal of Mathematics
PY  - 2018
SP  - 495 
VL  - 42
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/KJM_2018_42_4_a1/
LA  - en
ID  - KJM_2018_42_4_a1
ER  - 
%0 Journal Article
%A Ana Simić
%A Milena Bogdanović
%A Zoran Maksimović
%A Jelisavka Milošević
%T Fault-tolerant Metric Dimension Problem: A New Integer Linear Programming Formulation and Exact Formula for Grid Graphs
%J Kragujevac Journal of Mathematics
%D 2018
%P 495 
%V 42
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/KJM_2018_42_4_a1/
%G en
%F KJM_2018_42_4_a1
Ana Simić; Milena Bogdanović; Zoran Maksimović; Jelisavka Milošević. Fault-tolerant Metric Dimension Problem: A New Integer Linear Programming Formulation and Exact Formula for Grid Graphs. Kragujevac Journal of Mathematics, Tome 42 (2018) no. 4, p. 495 . http://geodesic.mathdoc.fr/item/KJM_2018_42_4_a1/