Fuzzy Minimum Spanning Tree Problem: A Greedy Algorithm using Quasi-Gaussian Fuzzy Weights

Madhushi Verma; K K Shukla

doi:10.37591/josettt.v1i3.211

Abstract

The classical Minimum Spanning Tree Problem (MST) deals with determining the spanning tree in a given undirected graph G(V, E) for which the sum of the weights assigned to the edges is minimum. The weights assigned to the edges are real numbers representing parameters like demand, cost, link capacity and distance which are not naturally precise and the uncertainty involved can be modelled using fuzzy numbers. There are several types of fuzzy numbers (like Triangular, Trapezoidal etc.) which provide for easy calculations but in this paper we have used Gaussian fuzzy numbers for two important reasons. Firstly, it is easy to analyse because it is continuous and differentiable and provides for efficient gradient based optimization and secondly it is simpler to represent because it requires fewer parameters. MST finds a lot of practical applications e.g. in network design (telephone, TV cables etc.), in cluster analysis and in solving problems like travelling salesman problem. It is beneficial to limit the support of the Gaussian function and derive a new category called Quasi-Gaussian Fuzzy Number (QGFN) and apply it to the MST problem. QGFN is finitely supported i.e. the value of x beyond- 3σl and+ 3 σr is set to zero whereis the modal value, σl and σr denote the left and right spreads, respectively corresponding to the Gaussian Distribution’s standard deviation. In this paper we have presented a greedy algorithm that uses QGFN and a Link Preference Index to solve MST intime using adjacency matrix, intime using binary heap and adjacency list and intime using Fibonacci heap and adjacency list.Keywords: Fuzzy minimum spanning tree, quasi-gaussian fuzzy number, linkpreference index