We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
FAULT-TOLERANT METRIC DIMENSION PROBLEM: A NEW INTEGER LINEAR PROGRAMMING FORMULATION AND EXACT FORMULA FOR GRID GRAPHS.
- Authors
SIMIĆ, ANA; BOGDANOVIĆ, MILENA; MAKSIMOVIĆ, ZORAN; MILOŠEVIĆ, JELISAVKA
- Abstract
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.
- Subjects
FAULT-tolerant computing; DIMENSIONS; PROBLEM solving; INTEGER programming; MATHEMATICAL formulas; GRAPH theory
- Publication
Kragujevac Journal of Mathematics, 2018, Vol 42, Issue 4, p495
- ISSN
1450-9628
- Publication type
Article
- DOI
10.5937/kgjmath1804495s