Pendekatan Matriks Ketetanggaan Berbobot untuk Solusi Minimum Spanning Tree (MST)
(1) Universitas Indraprasta PGRI
(2) Universitas Indraprasta PGRI
(*) Corresponding Author
Abstract
Minimum Spanning Tree (MST) or often called Minimum Weighting Spanning Tree (MWST) is a path or edge search algorithm that connects all vertices in a connected graph and does not form a circuit with a minimum weight. The classic algorithm used to solve MST problems is the Prim’s and Kruskal’s algorithms. The problem of minimum spanning tree is a problem related to optimization in finding the minimum weighted edge that can connect all vertices). MST is widely used in computer science such as to determine access points, build networks and many more. The purpose of this reserarch is to find new solutions that can provide alternative MST solutions besides classical algorithms such as Prim and Kruskal. This experimental research uses a weighted adjacency matrix approach, with weight taken from the minimum side in each pair of matrix to produce a minimum spanning tree. This new solution can be an alternative in solving the minimum spanning tree problems.
Keywords
Full Text:
PDFReferences
P. Jayawant and K. Glavin, “Minimum spanning trees,” Involv. a J. Math., vol. 2, no. 4, pp. 439–450, 2009.
A. Rahmawati and Mulyono, “Minimum Spanning Tree Pada Jaringan Pendistribusian,” UNNES J. Math., vol. 4, no. 2, 2015.
L. Caccetta, “The Modified CW1 Algorithm For The Degree Restricted Minimum Spanning Tree Problem,” vol. 1, no. 2, 2013.
M. Mismar, “A New Quick Algorithm for Finding The Minimal Spanning Tree A New Quick Algorithm for Finding the Minimal Spanning Tree,” no. March, 2018.
D. Vijayalakshmir and R. Kalaivani, “Minimum Cost Spanning Tree using Matrix Algorithm,” Int. J. Sci. Res. Publ., vol. 4, no. 9, pp. 1–5, 2014.
A. Y. Khedr and H. M. Bahig, “Debugging tool to learn algorithms: A case study minimal spanning tree,” Int. J. Emerg. Technol. Learn., vol. 12, no. 4, pp. 90–100, 2017.
T. Yamada, S. Kataoka, and K. Watanabe, “Listing all the minimum spanning trees in an undirected graph,” Int. J. Comput. Math., vol. 87, no. 14, pp. 3175–3185, 2010.
X. Wang, X. Wang, and D. M. Wilkes, “A divide-and-conquer approach for minimum spanning tree-based clustering,” IEEE Trans. Knowl. Data Eng., vol. 21, no. 7, pp. 945–958, 2009.
P. Biswas, M. Goel, H. Negi, and M. Datta, “An Efficient Greedy Minimum Spanning Tree Algorithm Based on Vertex Associative Cycle Detection Method,” Procedia Comput. Sci., vol. 92, pp. 513–519, 2016.
C. Contreras-Bolton, C. Rey, S. Ramos-Cossio, C. Rodríguez, F. Gatica, and V. Parada, “Automatically produced algorithms for the generalized minimum spanning tree problem,” Sci. Program., vol. 2016, 2016.
DOI: http://dx.doi.org/10.30998/string.v4i3.5900
Refbacks
- There are currently no refbacks.
Copyright (c) 2020 Tri Yani Akhirina
This work is licensed under a Creative Commons Attribution 4.0 International License.
STRING (Satuan Tulisan Riset dan Inovasi Teknologi) indexed by:
Ciptaan disebarluaskan di bawah Lisensi Creative Commons Atribusi 4.0 Internasional.
View My Stats