Pendekatan Matriks Ketetanggaan Berbobot untuk Solusi Minimum Spanning Tree (MST)

Tri Yani Akhirina; Thomas Afrizal

doi:10.30998/string.v4i3.5900

Pendekatan Matriks Ketetanggaan Berbobot untuk Solusi Minimum Spanning Tree (MST)

Tri Yani Akhirina^(1*), Thomas Afrizal⁽²⁾

(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

Minimum Spanning Tree; graf; Matriks Ketetanggan berbobot; Algoritma Prim; algoritma Kruskal

Full Text:

PDF

References

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