Indian Journal of Science and Technology
DOI: 10.17485/ijst/2015/v8i29/84011
Year: 2015, Volume: 8, Issue: 29, Pages: 1-4
Original Article
D. Jasmine Priskilla1* and K. Arulanandam2
1 Bharathiar University, Coimbatore – 641046, Tamil Nadu, India; [email protected]
2 Department of Computer Applications, GTM College, Gudiyattam – 632604, TamilNadu, India; [email protected]
Consider a directed weight graph G = (V, E) with n vertices and m edges. A directed minimum cost spanning tree of a weighted graph is a tree of the graph which contains all the vertices of the graph and the sum of weights of all its edges are minimum among all such possible trees of the directed graph. In this paper, I have proposed a new technique and its equivalent algorithm to construct the directed minimum cost spanning tree of a weight graph. This new algorithm is based on the weight matrix of a weighted graph. The input of the proposed algorithm is the weight matrix M, which consist n2 elements of directed weight graph G. The output of the algorithm is Directed Minimum Cost Spanning Tree. The best case time complexity will be in order of O(m), where m = n-1. The worst case time complexity will be in order of O(m2), where m = n-1.
Keywords: Directed Graph, Directed Minimum Cost Spanning Tree, Spanning Tree
Subscribe now for latest articles and news.
