SOME GREEDY BASED ALGORITHMS FOR MULTI PERIODS DEGREE CONSTRAINED MINIMUM SPANNING TREE PROBLEM

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.