Comparative Analysis of Structural-Based Reduction and Brute Force Algorithms for Determining Metric Dimensions in Tree Graphs - Afifah Farhanah Akadji; Abdul Gani F. S. H. Lihawa; Maharani Eka; Karina A. Sasmito; Hendy Prasetyo; Andi Sitti Dwi Auliyani (Journal of Digital Technology and Computer Science, 2026)
Purpose – This study aims to overcome the computational inefficiency of the Brute Force method in determining the metric dimension of tree graphs by evaluating the performance of a Structural-Based Reduction Algorithm. The study addresses the high computational cost of exhaustive search approaches and proposes a more efficient structural alternative. Methods – This research applies a comparative computational experimental approach by implementing both the Brute Force method and the proposed reduction algorithm on non-isomorphic tree graphs obtained from the McKay dataset. The algorithm is based on Slater’s theorem regarding leaves and stem vertices in tree graphs. Instead of testing all possible vertex combinations, the algorithm utilizes structural relationships to determine the metric dimension more efficiently. The comparison focuses on result consistency and computational execution time. Findings – Experimental results show that the proposed reduction algorithm achieves 100% accuracy, producing metric dimension values identical to those generated by the Brute Force method for all tested graphs. In terms of efficiency, the proposed method performs significantly better. For a tree graph with 20 vertices, the Brute Force method requires approximately 79 seconds, while the reduction algorithm completes the computation in only 0.005 seconds. Research implications – The findings indicate that structural analysis can reduce computational complexity in determining metric dimensions of tree graphs. However, the current approach is limited to acyclic graph structures and may require modification for cyclic graphs. Originality – This study introduces a deterministic and scalable alternative for determining metric dimensions in tree graphs through structural reduction principles.