Wamiliana, Wamiliana and Asmiati, Asmiati and Usman, Mustofa and Hijriani, Astria and Hastono, Wibi Cahyo (2018) Comparative Analysis of Some Modified Prim’s Algorithms to Solve The Multiperiod Degree Constrained Minimum Spanning Tree Problem. Indian Journal of Science and Technology, 11 (11). pp. 1-6. ISSN 0974-5645

Preview

Text Comparative Analysis of Some Modified Prim.....Indian Journal of Science and Technology.pdf Download (444kB) | Preview

Abstract

Objectives: To compare the WAC1, WAC2, and WAC3 algorithms against WADR1, WADR2, WADR3, WADR4, and WADR5 algorithms to solve the Multiperiod Degree Constrained Minimum Spanning Tree. Methods/Statistical analysis: WAC1, WAC2, and WAC3 are algorithms developed by modifying Prim’s algorithm for the Minimum Spanning Tree (MST) and adopting the period of installation/connecting for vertices in the network. In WAC1, WAC2, and WAC3 algorithms we consider the HVTk, the set of vertices that must be connected on kth period, while in WADR5 is not. In WAC1 the vertices in HVTk must be installed as early as possible, while in WAC2 is not given priority to be connected as soon as possible, but can be any time as long as the connection still on that current period. In WAC3 we adopt the smallest value for 2-path for vertex under consideration to be connected. All algorithm proposed used the same data as used in WADR1, WADR2,WADR3, WADR4 and WADR5. Findings: Since WAC1, WAC2, and WAC3, WADR5 algorithms are based on modified Prim’s algorithm, then the connectivity property is maintained during the process of installation/connection not like WADR1, WADR2, WADR3, and WADR4 where based on Kruskal’s. Based on the same data used and connectivity property, the result shows that the performance of WAC2 is the best among the other algorithms developed. Application/Improvements: Considering real-life application in the network installation problem, the WAC2 algorithm is one of alternative solutions since it maintains connectivity property and performs best. Keywords: comparative analysis, Modified Prim, degree constrained, multiperiod, connectivity

Item Type:	Article
Subjects:	Q Science > QA Mathematics
Divisions:	Fakultas Matematika dan Ilmu Pengetahuan Alam (FMIPA) > Prodi Matematika
Depositing User:	WAMILIANA
Date Deposited:	20 Mar 2018 08:36
Last Modified:	20 Mar 2018 08:36
URI:	http://repository.lppm.unila.ac.id/id/eprint/6613

Actions (login required)

View Item