Article Per Year (5 Year)
p-Index From 2020 - 2025
0.23
P-Index
This Author published in this journals
All Journal Indonesian Journal of Mathematics and Applications
Imran, Nurain
Unknown Affiliation
Computer Science & IT Education Mathematics Other

Published : 1 Documents Claim Missing Document
Claim Missing Document
Check
Articles

Found 1 Documents
Search

 1 
Implementation of Graph Coloring on the Map of North Gorontalo District Using the D’Satur Algorithm and the Backtracking Algorithm Imran, Nurain; Achmad, Novianita; Asriadi, Asriadi; Yahya, Nisky Imansyah; Nasib, Salmun K.; Katili, Muh Rifai
Indonesian Journal of Mathematics and Applications Vol. 3 No. 2 (2025): Indonesian Journal of Mathematics and Applications (IJMA)
Publisher : Universitas Brawijaya

Show Abstract | Download Original | Original Source | Check in Google Scholar | DOI: 10.21776/ub.ijma.2025.003.02.5

Abstract

Graph Coloring is the process of assigning colors to vertices such that no adjacent vertices share the same color, using the minimal number of colors possible. This study aims to implement graph coloring to the map of North Gorontalo Regency, which consists of 11 sub-districts and 123 villages, utilizing the D’Satur and Backtracking algorithms. It also compares the algorithms in terms of the smallest chromatic number and identifies strategic points in North Gorontalo Regency, particularly in sub-districts, based on the number of adjacent vertices. The study employed a case study method to gather information, specifically the map of North Gorontalo Regency. The results demonstrate that graph coloring of the map utilizing the D’Satur algorithm produces a chromatic number of (χ = 3) for sub-districts and (χ = 5) for villages. Meanwhile, the Backtracking algorithm yields a chromatic number of (χ = 3) for districts and (χ = 4) for villages. Thus, for sub-district coloring, both algorithms yield the same chromatic number. However, the Backtracking algorithm performs better for village coloring, as it produces the smallest chromatic number. The identified strategic sub-district is Kwandang, which has the highest degree of 4.
Co-Authors Asriadi Asriadi Muhammad Rifai Katili NISKY IMANSYAH YAHYA Salmun K. Nasib