Open Access Open Access  Restricted Access Subscription Access
Open Access Open Access Open Access  Restricted Access Restricted Access Subscription Access

Constructing Minimum Spanning Tree Based on Hierarchical Clustering


Affiliations
1 C.C.M.R. Polytechnic College, Thanjavur-613003, India
2 E.G.S. Pillay Engineering College, Nagapattinam, India
     

   Subscribe/Renew Journal


A "graph" refers to a collection of vertices or nodes and a collection of edges that connect pairs of vertices. A graph may be undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another. Spanning Tree is a tree that connects all vertices in the graph. In a single graph, we can have many number of spanning tree. A minimum spanning tree (MST) is then a spanning tree with edge cost less than or equal to the cost of every other spanning tree. Several algorithms have been proposed to find minimum spanning tree. Considering the entire graph to construct MST is a difficult task since the number of nodes increases then the complexity also increases and is vice versa. So here we apply divide and conquer approach to split the nodes into several groups (clusters) and then MST is performed to each cluster and finally clusters are connected. Several clustering algorithms are used for distance based clustering here we prefer to take hierarchical clustering algorithm to find minimum spanning tree. Present work the authors conclude that performance of hierarchical clustering is better than that of other techniques. The experimental results of the performance outcome of the hierarchical are so better that the K mean clustering technique.

Keywords

Hierarchical Clustering, MST, K Means Clustering.
User
Subscription Login to verify subscription
Notifications
Font Size

Abstract Views: 234

PDF Views: 1




  • Constructing Minimum Spanning Tree Based on Hierarchical Clustering

Abstract Views: 234  |  PDF Views: 1

Authors

M. A. Arunagiri
C.C.M.R. Polytechnic College, Thanjavur-613003, India
K. Kumaran
E.G.S. Pillay Engineering College, Nagapattinam, India
N. Murali
E.G.S. Pillay Engineering College, Nagapattinam, India

Abstract


A "graph" refers to a collection of vertices or nodes and a collection of edges that connect pairs of vertices. A graph may be undirected, meaning that there is no distinction between the two vertices associated with each edge, or its edges may be directed from one vertex to another. Spanning Tree is a tree that connects all vertices in the graph. In a single graph, we can have many number of spanning tree. A minimum spanning tree (MST) is then a spanning tree with edge cost less than or equal to the cost of every other spanning tree. Several algorithms have been proposed to find minimum spanning tree. Considering the entire graph to construct MST is a difficult task since the number of nodes increases then the complexity also increases and is vice versa. So here we apply divide and conquer approach to split the nodes into several groups (clusters) and then MST is performed to each cluster and finally clusters are connected. Several clustering algorithms are used for distance based clustering here we prefer to take hierarchical clustering algorithm to find minimum spanning tree. Present work the authors conclude that performance of hierarchical clustering is better than that of other techniques. The experimental results of the performance outcome of the hierarchical are so better that the K mean clustering technique.

Keywords


Hierarchical Clustering, MST, K Means Clustering.