COMPUTATIONAL ASPECTS OF GREEDY ALGORITHM FOR SOLVING THE MULTI PERIOD DEGREE CONSTRAINED MINIMUM SPANNING TREE PROBLEM
Given one center already set, The Multi Period Degree Constrained Minimum Spanning Tree Problem (MPDCMST) is a problem of determining how many vertices (can be computers, cities, and so on) should be installed in a certain period in such a way so that the cost of installation is minimum. After all the periods done, all of the vertices must be in the network, and still the cost of installation must be the minimum. In addition, the network itself has a degree restriction in every vertex which limits the number of links that incident to. In this paper we will discuss the algorithm we have developed and give results on 600 random table data.
Keywords: multi period, degree constrained, minimum spanning tree
Article MetricsAbstract view : 679 times
PDF - 343 times
- There are currently no refbacks.