ALGORITMA GREEDY COLORING PADA WEBSITE ENSIKLOPEDIA PETA
Nasional University
Indonesia
Nasional University
Indonesia
Abstract
Graph coloring is used, because the results of graph coloring can be used in several systems, such as the scheduling and the coloring of map areas in this study. The goal in implementing graph coloring here is to get as few colors as possible in the 44 borders of villages in Jakarta Pusat. The problem of coloring graphs on the Jakarta Pusatโs villages map uses a greedy algorithm that exists on web-based maps and makes encyclopedias to support descriptions of areas that have been colored. The greedy algorithm is a form of algorithm that is currently developing in optimization problems by forming a step-by-step solution. Greedy algorithm can be applied to resolve the problem of graph coloring. The best solution to answer a graph coloring problem is to determine the chromatic number ๐(๐บ) using the greedy algorithm. Graph coloring on a map is done using a greedy algorithm to obtain the minimum number of colors possible without adjacent regions using the same color. Based on the research results, the least number of colors used in coloring the village map in Central Jakarta, which consists of 44 areas, is 6 types of colors.
Keywords
References
Angelina, C., Koban, N., & Nudin, S. R. (2020). Penerapan Graph Coloring Menggunakan Algoritma
Greedy Pada Aplikasi Pemesanan Tiket Kapal Penyeberangan. Journal of Informatics and
Computer Science, 02.
Dhulipala, L., Blelloch, G. E., & Shun, J. (2021). Theoretically Efficient Parallel Graph Algorithms Can Be
Fast and Scalable. ACM Transactions on Parallel Computing, 8(1).
https://doi.org/10.1145/3434393
Fakhri, M. Y., Harahap, E., & Badruzzaman, F. H. (2021). Implementasi Algoritma Welch-Powell pada
Pengaturan Lampu Lalu Lintas Pasteur Bandung. Jurnal Riset Matematika, 1(2), 91โ98.
https://doi.org/10.29313/jrm.v1i2.365
Irsal, K. (n.d.). PEWARNAAN GRAF PADA PETA MENGGUNAKAN ALGORITMA GREEDY (Studi Kasus :
Peta Provinsi DKI Jakarta).
Kumar Gupta, S., Singh, G. &, Gupta, S., & Singh, D. P. (2020). Greedy Graph Coloring Algorithm Based
on Depth First Search. International Journal on Emerging Technologies, 11(2), 854โ862.
https://www.researchgate.net/publication/341371807
Marappan, R., & Sethumadhavan, G. (2020). Complexity analysis and stochastic convergence of some
well-known evolutionary operators for solving graph coloring problem. Mathematics, 3.
https://doi.org/10.3390/math8030303
Slamin, S., Adiwijaya, N. O., Hasan, M. A., Dafik, D., & Wijaya, K. (2020). Local super antimagic total
labeling for vertex coloring of graphs. Symmetry, 12(11), 1โ17.
https://doi.org/10.3390/sym12111843
Sopiyan, M., Gunaryati, A., & Fitri, I. (2022). Graph coloring Sistem Pendaftaran dan Proses
Penjadwalan Data Instruktur Berbasis Web dengan Algoritma Welch-powell. Jurnal Teknologi
Informasi Dan Komunikasi), 6(1), 2022. https://doi.org/10.35870/jti
Surbakti, N. M., & Ramadhani, F. (2022). Implementation of the Greedy Algorithm for Coloring Graph
Based on Four-Color Theorem. Sudo Jurnal Teknik Informatika, 1(4), 178โ182.
https://doi.org/10.56211/sudo.v1i4.157
Tian, Y., Khosoussi, K., Rosen, D. M., & How, J. P. (2021). Distributed Certifiably Correct Pose-Graph
Optimization. IEEE Transactions on Robotics, 37(6), 2137โ2156.
https://doi.org/10.1109/TRO.2021.3072346
Wang, Y., Cai, S., Pan, S., Li, X., & Yin, M. (n.d.). Reduction and Local Search for Weighted Graph
Coloring Problem. www.aaai.org
