Two Phase Heuristic Algorithm for Mean Delay constrained Capacitated Minimum Spanning Tree Problem


KIPS Transactions on Computer and Communication Systems, Vol. 10, No. 3, pp. 367-376, Jun. 2003
10.3745/KIPSTC.2003.10.3.367,   PDF Download:

Abstract

This study deals with the DCMST (Delay constrained Capacitated Minimum Spanning Tree) problem applied in the topological design of local networks or finding several communication paths from root node. While the traditional CMST problem has only the traffic capacity constraint served by a port of root node, the DCMST problem has the additional mean delay constraint of network. The DCMST problem consists of finding a set of spanning trees to link end-nodes to the root node satisfying the traffic requirements at end-nodes and the required mean delay of network. The objective function of problem is to minimize the total link cost. This paper presents two-phased heuristic algorithm, which consists of node exchange, and node shift algorithm based on the trade-off criterions, and mean delay algorithm. Actual computational experience and performance analysis show that the proposed algorithm can produce better solution than the existing algorithm for the CMST problem to consider the mean delay constraint in terms of cost.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
Y. J. Lee, "Two Phase Heuristic Algorithm for Mean Delay constrained Capacitated Minimum Spanning Tree Problem," KIPS Journal C (2001 ~ 2012) , vol. 10, no. 3, pp. 367-376, 2003. DOI: 10.3745/KIPSTC.2003.10.3.367.

[ACM Style]
Yong Jin Lee. 2003. Two Phase Heuristic Algorithm for Mean Delay constrained Capacitated Minimum Spanning Tree Problem. KIPS Journal C (2001 ~ 2012) , 10, 3, (2003), 367-376. DOI: 10.3745/KIPSTC.2003.10.3.367.