Open AccessAn efficient method to solve least-cost minimum spanning tree (LC-MST) problem
Author(s) -
M. R. Hassan
Publication year - 2011
Publication title -
journal of king saud university - computer and information sciences
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.617
H-Index - 33
eISSN - 2213-1248
pISSN - 1319-1578
DOI - 10.1016/j.jksuci.2011.12.001
Subject(s) - minimum spanning tree , distributed minimum spanning tree , spanning tree , kruskal's algorithm , reverse delete algorithm , euclidean minimum spanning tree , mathematical optimization , tree (set theory) , computer science , mathematics , algorithm , combinatorics
In this paper, least-cost minimum spanning tree (LC-MST) problem is defined as a method to construct a minimum cost spanning tree that has the least-cost edges in the network by using the distance (cost) matrix. The paper presents a new algorithm based on the distance matrix to solve the LC-MST problem. The studied cases show that the presented algorithm is efficient to solve the LC-MST problem in less time. Also, the presented algorithm can be modified to solve the DC-MST (Delay Constrained-Minimum Spanning Tree) problem presented by Lee and Atiquzzaman (2007) and the MRCT (Minimum Routing Cost Tree) problem presented by Cambos and Ricardo (2008), given as the applications of the presented algorithm
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom