USING MODIFICATION OF PRIM’S ALGORITHM AND GNU OCTAVE AND TO SOLVE THE MULTIPERIODS INSTALLATION PROBLEM

Keywords: Multi Periods, Degree Constrained, Minimum Spanning Tree, Prims’ Algorithms, GNU OCTAVE

Abstract

The Minimum Spanning Tree (MST) is one of the famous problems that is used mostly as the backbone in many network design problems. Given a graph G(V,E), where V is the set of vertices and E is the set of edges connecting vertices in V, and for every edge eij there is an associated weight cij ≥0. The Multi Period Degree Constrained Minimum Spanning Tree (MPDCMST) is a problem of finding an MST while also considering the degree constrained on every vertex, and satisfying vertices installation requirement on every period. Two algorithms (WWM1 and WWM2) are proposed for solving this problem. GNU OCTAVE is used for coding and visualization. GNU is a recursive acronym for "GNU's Not Unix!", and that name is chosen because it is like Unix but differs from Unix because it is free and contains no Unix code. Those algorithms were implemented using 300 randomly generated problems. Moreover, we compare WWM1 and WWM2 algorithms using existing data from the literature and the results show that WWM2 is the best.

ABSTRAK: Minimum Spanning Tree (MST) merupakan salah satu masalah mahsyur yang banyak digunakan sebagai tulang belakang kepada masalah banyak rekaan jaringan. Menerusi graf G(V,E), di mana V adalah himpunan titik dan E adalah himpunan garis yang menghubungkan titik-titik dalam V, dan bagi setiap garis eij terdapat berat berhubung cij ≥0, Multi-period Degree Constrained Minimum Spanning Tree (MPDCMST) merupakan masalah dalam menentukan MST, pada masa sama turut menimbangkan kekangan pada setiap titik vertek, dan memenuhi syarat keperluan pemasangan pada setiap detik. Dua algoritma (WWM1 dan WWM2) dicadangkan bagi menyelesaikan masalah ini. GNU OCTAVE digunakan bagi pengaturcaraan dan visualisasi.  GNU merupakan suatu singkatan kepada “GNU's Not Unix”, dan nama tersebut dipilih karena ianya seperti Unix, tetapi berbeza dari Unix kerana ia percuma dan tidak mempunyai kod Unix. Algoritma tersebut dilaksana dengan menggunakan 300 masalah terhasil secara rawak. Tambahan, algoritma WWM1 dan WWM2 dibandingkan dengan kajian terdahulu dan hasil kajian menunjukkan WWM2 adalah terbaik.

 

Downloads

Download data is not yet available.

References

Gabow H.N and R.E. Tarjan.(1984) Efficient algorithms for a family of matroid intersection problems. Journal of Algorithms, 5:80-131.

Garey, M.R.,and Johnson, D.S.(1979) Computers and Intractibility, A Guide to the Theory of NP-Completeness. Freemann, San Francisco.

Narula, S.C., and C. A.Ho.(1980) Degree-Constrained Minimum Spanning Tree. Computer and Operation Research, 7:239-249.

Krishnamoorthy, M.,A.T. Ernst and Y. M Sharaila.(2001) Comparison of Algorithms for the Degree Constrained Minimum Spanning Tree. Journal of Heuristics, 7(6): 587-611.

Deo N. and N. Kumar.(1997) Computation of Constrained Spanning Trees: A Unified Approach. Network Optimization ( Lecture Notes in Economics and Mathematical Systems. Editor : Panos M. Pardalos, et al. ,Springer-Verlag, Berlin, Germany: 194 – 220.

Zhou, G. and M Gen. (1997) A Note on Genetics Algorithms for Degree- Constrained Spanning Tree Problems. Networks, Vol. 30: 91 – 95.

Wamiliana. (2004) Solving the Degree Constrained Minimum Spanning Tree Using Tabu and Penalty Method. Jurnal Teknik Industri:1-9.

Caccetta L. and Wamiliana.(2001) Heuristics Algorithms for the Degree Constrained Minimum Spanning Tree Problems.Proceeding of the International Congress on Modelling and Simulation (MODSIM),Canberra, Editors: F. Ghassemi et.al:2161-2166.

Wamiliana and L. Caccetta. (2003)Tabu search Based Heuristics for the Degree Constrained Minimum Spanning Tree Problem.Proceeding of South East Asia Mathematical Society:133-140.

Wamiliana and L. Caccetta.(2012) The Modified CW1 Algorithm for The Degree Restricted Minimum Spanning Tree Problem, Proceeding of International Conference on Engineering and Technology Development, Bandarlampung 20-21 June:36-39.

Kawatra R. (2002)A multi period degree constrained Minimum Spanning Tree Problem, European Journal of Operational Research,143: 53 – 63.

[Wamiliana, D. Sakethi, and R. Yuniarti,(2010) Computational Aspect of WADR1 and WADR2 Algorithms for The Multi Period Degree Constrained Minimum Spanning Tree Problem. Proceeding SNMAP, Bandar lampung 8 – 9 December:208 – 214.

Wamiliana, Amanto, and M. Usman.(2013) Comparative Analysis for The Multi Period Degree Constrained Minimum Spanning Tree Problem. Proceeding The International Conference on Engineering and Technology Development (ICETD):39 – 43.

]Wamiliana, F. A.M. Elfaki, M. Usman, and M. Azram. (2015) Some Greedy Based Algorithms for Multi Periods Degree Constrained Minimum Spanning Tree Problem. ARPN Journal of Engineering and Applied Sciences, 2015: 10 (21): 10147 – 10152.

Wamiliana, M. Usman, D. Sakethi, R. Yuniarti, and A. Cucus.(2015) The Hybrid of Depth First Search Technique and Kruskal’s Algorithm for Solving The Multiperiod Degree Constrained Minimum Spanning Tree Problem. The 4th International Conference on Interactive Digital Media (ICIDM). IEEE Explore, Dec 2015

Wamiliana, Asmiati, M. Usman, A. Hijriani, and W. C. Hastono. (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):1-6.

Wamiliana, Warsono, Asmiati, A. Hijriani, and W. C. Hastono.(2018) Different Time Installation Effect on The Quality Of The Solution For The Multiperiod Installation Problem Using Modified Prim’s Algorithm. Far East Journal of Electronics and Communications, 18(2): 291-300.

GNU Octave. Available: https://www.gnu.org/software/octave.

Published
2020-01-20
How to Cite
Wamiliana, W., Usman, M., Warsito, W., Warsono, W., & Daoud, J. I. (2020). USING MODIFICATION OF PRIM’S ALGORITHM AND GNU OCTAVE AND TO SOLVE THE MULTIPERIODS INSTALLATION PROBLEM. IIUM Engineering Journal, 21(1), 100 - 112. https://doi.org/10.31436/iiumej.v21i1.1088
Section
Engineering Mathematics and Applied Science