EUVIMEDEUVIMED entdecken
Open Access · CC BY-SA 4.0

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 · 25.05.2026 · 90-99

DOI: 10.66053/dtcs.v3i2.696 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Journal of Digital Technology and Computer Science, online erschienen am 25.05.2026. Verfasst von Afifah Farhanah Akadji und 5 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY-SA 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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.

Zitieren

APA

Akadji, A. F., Lihawa, A. G. F. S. H., Eka, M., Sasmito, K. A., Prasetyo, H., & Auliyani, A. S. D. (2026). Comparative Analysis of Structural-Based Reduction and Brute Force Algorithms for Determining Metric Dimensions in Tree Graphs. Journal of Digital Technology and Computer Science, 90-99. https://doi.org/10.66053/dtcs.v3i2.696

Vancouver

Akadji AF, Lihawa AGFSH, Eka M, Sasmito KA, Prasetyo H, Auliyani ASD. Comparative Analysis of Structural-Based Reduction and Brute Force Algorithms for Determining Metric Dimensions in Tree Graphs. Journal of Digital Technology and Computer Science. 2026:90-99. doi:10.66053/dtcs.v3i2.696

BibTeX
@article{Akadji2026,
  author = {Akadji, Afifah Farhanah and Lihawa, Abdul Gani F. S. H. and Eka, Maharani and Sasmito, Karina A. and Prasetyo, Hendy and Auliyani, Andi Sitti Dwi},
  title = {Comparative Analysis of Structural-Based Reduction and Brute Force Algorithms for Determining Metric Dimensions in Tree Graphs},
  journal = {Journal of Digital Technology and Computer Science},
  year = {2026},
  pages = {90--99},
  doi = {10.66053/dtcs.v3i2.696}
}
Kostenlos starten →