Pengembangan Algoritma Prim untuk Menentukan Minimum Spanning Forest

Authors

  • Hari Sumardi Universitas Bengkulu
  • Afnaria Afnaria Universitas Islam Sumatera Utara
  • Suvriadi Panggabean Universitas Muhammadiyah Sumatera Utara

DOI:

https://doi.org/10.36815/majamath.v4i1.968

Keywords:

MST, Forest, Algoritma prim, MSF

Abstract

Minimum spanning tree (MST) merupakan salah satu permasalahan dalam teori graph. MST dari graph G  adalah spanning tree dengan total bobot sisi terkecil pada suatu graph berbobot G yang terhubung. Terdapat dua algoritma klasik di dalam MST yakni algoritma Kruskal dan Prim. Kedua algoritma tersebut dapat menghasilkan sebuah MST. Forest merupakan graph yang terdiri dari beberapa tree. Spanning forest dari graph tak terhubung G merupakan forest yang dibangun dari graph G. Minimum spanning forest (MSF) dari graph G merupakan spanning forest dengan total bobot sisi terkecil atas semua spanning forest pada graph G. Pada hasil, penulis menyajikan sebuah algoritma MSF yang dikembangkan dari algoritma Prim.

References

Ahani, I.K., Salari, M., Hosseini, S.M., & Iori, M. (2020). Solution of Minimum Spanning Forest Problems with Reliability Constraints. Computers & Industrial Engineering. 142 (2020) 106365, 1-13.
Berganti?os, G., & Vidal-Puga, J. (2011). The Folk Solution and Boruvka’s Algorithm in Minimum Cost Spanning Tree Problems. Discrete Applied Mathematics, 159 (2011), 1279-1283.
Bollig, B. (2012). On Symbolic OBDD-Based Algorithms for The Minimum Spanning Tree Problem. Theoretical Computer Science, 447 (2012), 2-12.
Bona, M. (2006). A Walk Through Combinatorics, An Introduction to Enumerat-ion and Graph Theory, Second Edition. World Scientific, Singapore.
Brualdi, R. A. (2010). Introductory Combinatorics (Fifth Edition). China Machine Press, China.
Coletti, P. (2016). Comparing Minimum Spanning Trees of The Italian Stock Market Using Returns and Volumes. Physica A, 463 (2016), 246-261.
Hardianto. (2015). Penentuan Penurunan Tegangan Berdasarkan Minimum Spanning Tree Pada Jaringan Listrik Distribusi Primer. Emitor: Jurnal Teknik Elektro, 15 (01), 1-10.
Hassan, M. R. (2012). An Efficient Method to Solve Least-Cost Minimum Spanning Tree (LC-MST) problem. Computer and Information Sciences, (2012) 24, 101-105.
Korte, B., & Vygen, J. (2006). Combinatorial Optimization, Theory and Algorithm, Third Edition. Springer, New York.
Li, W. V., & Zhang, X. (2010). Expected Lengths of Minimum Spanning Trees for Non-Identical Edge Distributions. Electronic Journal of Probability, 15(5), 110-141.
Marpaung, F., & Arnita. (2020). Comparative of Prim’s and Boruvka’s Algorithm to Solve Minimum Spanning Tree Problems. Journal of Physics: Conf. Series, 1462 (2020) 012043, 1-8.
Murmu, M. K. (2015). A Distributed Approach to Construct Minimum Spanning Tree in Cognitive Radio Networks. Procedia Computer Science, 70 (2015), 166-173.
Pike, R., Sechopoulos, I., & Fei, B. A. (2015). Minimum Spanning Forest Based Classification Method for Dedicated Breast CT Images. Med. Phys, 42 (11), 6190-6202.
Sam, M., & Yuliani. (2016). Penerapan Algoritma Prim Untuk Membangun Pohon Merentang Minimum (Minimum Spanning Tree) Dalam Pengoptimalan Jaringan Transmisi Nasional Provinsi Sulawesi Selatan. Jurnal Dinamika, 07 (1), 50-61.
Yasin, M., & Afandi, B. (2014). Simulasi Minimum Spanning Tree Graf Berbobot Menggunakan Algoritma Prim dan Algoritma Kruskal. Eucazione, 2 (2), 121-130.
Yudasril, Amalia, I. S., & Hasanah, A. (2018). “PRIMATHRIC”: Aplikasi algoritma Prim Untuk Optimasi Penyediaan Akses Energi Listrik di Kabupaten Alor. Jurnal Matematika Integratif. 14 (2), 123-134.

Downloads

Published

2021-03-25