The hybrid of depth first search technique and Kruskal's algorithm for solving the multiperiod degree constrained minimum spanning tree problem

摘要

Given edge weighted graph G(V,E) (all weights are nonnegative) where vertices can represent terminals, cities, etc., and edges can represent cables, road, etc., the Multi Period Degree Constrained Minimum Spanning Tree Problem (MPDCMST) is a problem of finding the total minimum installation cost whilst also maintaining the maximum number of edges incidence to every vertex. The restriction of the links on every vertex occurs to keep the reliability of the network. Moreover, the installation process also divided into some periods due to fund limitation. In this research we will discuss the hybrid between the depth first search technique and Kruskal's Algorithm applying to solve the MPDCMST problem.