Some greedy based algorithms for multi periods degree constrained minimum spanning tree problem

Wamiliana, Wamiliana and Elfaki, Faiz Ahmed Mohamed and Usman, Mustofa and Azram, Mohammad (2015) Some greedy based algorithms for multi periods degree constrained minimum spanning tree problem. ARPN Journal of Engineering and Applied Sciences, 10 (21). pp. 10147-10152. ISSN 1819-6608

PDF - Published Version Restricted to Repository staff only Download (191kB) | Request a copy

Abstract

In Indonesia, the fund for a project or an activity is usually divided into terms which can be two or three terms. Therefore, in order to optimize the utility, the team of the project need to design the project so that the project can be used as soon as possible without violating the restriction given by the government. The Multi Periods Degree Constrained Minimum Spanning Tree Problem (MPDCMST) is a problem that concerns about finding a minimum networks installations for a certain commodity so that the networks does not violate the reliability restriction whilst also satisfying the fund limitation in every stages of installations. In this paper we proposed three algorithms by modifying Kruskal’s and Prim’s algorithms. We implemented our algorithms on 300 generated problems with vertex order ranging from 10 to 100, and compared them with those that were already in the literature. The result shows that the algorithms proposed perform better.

Item Type:	Article (Journal)
Additional Information:	4925/46124
Uncontrolled Keywords:	multi periods, degree constrained, installations, networks.
Subjects:	Q Science > QA Mathematics
Kulliyyahs/Centres/Divisions/Institutes (Can select more than one option. Press CONTROL button):	Kulliyyah of Engineering > Department of Science
Depositing User:	Dr faiz elfaki
Date Deposited:	18 Dec 2015 10:29
Last Modified:	25 Jun 2018 09:07
URI:	http://irep.iium.edu.my/id/eprint/46124

Actions (login required)

View Item