Comparative Analysis for The Multi Period Degree Minimum Spanning Tree Problem

. Wamiliana, . Amanto, Mustofa Usman

Abstract


The Multi Period Degree Constrained Minimum Spanning Tree Problem (MPDCMST) concerns of finding the total minimum cost of networks installation, where the installation process is divided into some periods. In the beginning of installation process, thecenter of the networks already set (as server, reservoir, etc). The installation process is divided into some period due to some factors, usually fund limitation. During the installation process, the networks is supposed to be maintained its reliability by restrict the numbers of links that can be connected to the node that already in the networks. In this paper we will discuss and improve the performance of WADR1 and WADR2 algorithms by setting the number of elements in the set of vertices that must be in installed in a certain period as a fix number and adding the length of the path in DFS. The result shows that the modifications works better. 

Keywords


Multi perio; degree constrained; minimum spanning tree; comparative analysis

Full Text:

PDF PDF

References


. Boldon, B., N. Deo and Nishit Kumar (1996). ‘ Minimum Weight degree-constrained spanning tree problem: Heuristics and Implementation on an SIMD parallel machine’, Parallel Computing vol. 22, pp.369 –382.

.Caccetta L., and Wamiliana, 2001. Heuristics Algorithms for The Degree Constrained Minimum Spanning Tree Problem, in Proceeding of The International Congress on Modeling and Simulation (MODSIM 2001), Canberra. Editor : F. Ghassemi et al. , pp. 2161-2166.

.Deo,N. and Nishit 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, pp. 194 – 220.

.Graham, R.L., and Hell, P., ‘ On the history of the Minimum Spanning Tree Problem’, 1982. Mimeographed, Bell Laboratories, Murray Hill, New Jersey

. Junaidi, A.., Wamiliana, Dwi Sakethi, and Edy Tri Baskoro, 2008. Computational Aspect of Greedy Algorithm for The Multi Period Degree Constrained Minimum Spanning Tree Problem, Jurnal Sains MIPA, Special Edition Vol. 14 No. 1. Pp 1-6

Krishnamoorthy, M., A.T. Ernst and Yazid M Sharaila (2001), ‘Comparison of Algorithms for the Degree Constrained Minimum Spanning Tree’, Journal of Heuristics, Vol. 7, no. 6, pp. 587-611.

.Kawatra, 2002.A multi period degree constrained Minimum Spanning Tree Problem, European Journal of Operational Research, Vol 143, pp. 53 – 63.

. Narula,S. C., and Cesar A.Ho, 1980. ‘ Degree-Constrained Minimum Spanning Tree’, Computer and Operation Research , Vol. 7,pp. 239-249

. Wamiliana,2002. Combinatorial Methods for Degree Constrained Minimum Spanning Tree Problem, Doctoral Thesis, Department of Mathematics and Statistics, Curtin University and Technology, Australia.

. Wamiliana, 2002. ‘The Modified Penalty Methods for The Degree Constrained Minimum Spanning Tree Problem’, Jurnal Sains dan Teknologi, Vol. 8, pp.1-12.

. Wamiliana, 2004. ‘Solving the Degree Constrained Minimum Spanning Tree Using Tabu and Penalty Method’, Jurnal Teknik Industri, pp.1-9.

Wamiliana and Caccetta. 2003. “Tabu search Based Heuristics for the Degree Constrained Minimum Spanning Tree Problem,Proceeding of South East Asia Mathematical Society, pp. 133-140

Wamiliana, Dwi Sakethi, Akmal J, and Edy Tri Baskoro, 2005. The Design of Greedy Algorithm for Solving The Multi Period degree Constrained Minimum Spanning Tree Problem, Jurnal sains dan Teknologi Vol 11 No. 2, pp. 93 – 96.

Wamiliana and L. Caccetta, 2006. Computational Aspects of The Modified Penalty for Solving The Degree Constrained Minimum Spanning Tree Problem, Journal of Quantitatve Methods Vol. 2 No. 2 pp. 10 – 16.

Wamiliana, Dwi sakethi, and Restu Yuniarti, 2010. Computational Aspect of WADR and WADR2 Algorithms for The Multi Period Degree Constrained Minimum Spanning Tree Problem, Proceeding SNMAP 2010, pp. 208 – 214.

Wamiliana, 2013. Computational Aspect of Modified Kruskal Algorithms for Degree Restricted Minimum Spanning Tree Problem, The 5th International Conference on Numerical Optimizations and Operations Research (ICNOOR-V), Banda Aceh, 26 – 28 June, 2013.

Zhou G., and Mitsuo Gen, 1997. A Note on Genetic Algorithms for The Degree Constrained Minimum Spanning Tree Problem, Networks, Vol. 30, pp. 91-95.


Refbacks

  • There are currently no refbacks.


International Conference on Engineering and Technology Development (ICETD)
Bandar Lampung University
ISSN: 2301-5690