Pengembangan Algoritma Prim untuk Menentukan Minimum Spanning Forest
DOI:
https://doi.org/10.36815/majamath.v4i1.968Keywords:
MST, Forest, Algoritma prim, MSFAbstract
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
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
Issue
Section
License
Seluruh artikel di jurnal ini dapat disebarluaskan dengan tetap mencamtumkan sumber yang sah. Identitas judul artikel tidak boleh dihilangkan. Penerbit tidak bertanggung jawab terhadap naskah yang diplubikasikan. Isi artikel menjadi tanggung jawab penulis.
