Open Access Open Access  Restricted Access Subscription or Fee Access

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

Madhushi Verma, K K Shukla

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 where
is 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 in
time using adjacency matrix, in
time using binary heap and adjacency list and in
time using Fibonacci heap and adjacency list.

Keywords: Fuzzy minimum spanning tree, quasi-gaussian fuzzy number, link
preference index


Full Text:

PDF

References


Bang W.Y., Kun C.M. 2006. Minimum Spanning Trees. Available from: http://www.csie.ntu.edu.tw/~kmchao/tree07spr/mst.pdf.

Blue M., Bush B., Puckett J. Unified Approach to Fuzzy Graph Problems. Fuzzy Set. Syst. 2002; 125: 355–368p.

Elizabeth S., Sujatha L. Fuzzy Shortest Path Problem Based on Index Ranking. J. Math. Res. 2011; 3(4). 80–88p.

Wu. Dongrui. Twelve Considerations in Choosing between Gaussian and Trapezoidal Membership Functions in Interval Type-2 Fuzzy Logic Controllers. IEEE International Conference on Fuzzy Systems, Brisbane, Australia, 2012.

Grauel A., Ludwig L.A. Construction of Differentiable Membership Functions. Fuzzy Set. Syst. 1999; 101(2): 219–225p.

Kashtiban M.M., Khoei A., Kh. Hadidi. Optimization of Rational-Powered Membership Functions Using Extended Kalman Filter. Fuzzy Set. Syst. 2008; 159(23): 3232–3244p.

Garibaldi J.M., John R.I. Choosing Membership Functions of Linguistic Terms. IEEE International Conference on Fuzzy Systems (FUZZ-IEEE 2003), 2003; 1: 578–583p.

Kreinovich V., Quintana C., Reznik L. Gaussian Membership Functions are Most Adequate in Representing Uncertainty in Measurements. Proceedings of NAFIPS'92: North American Fuzzy Information Processing Society Conference, Puerto Vallarta, 1992.

Prim R.C. Shortest Connection Networks and Some Generalizations. Bell Syst. Technol. J. 1957; 36: 1389–1401p.

Kruskal J.B. On the Shortest Spanning Subtree of a Graph and the Travelling Salesman Problem. Proceedings of the American Mathematical Society, 1956, 71: 48–50p.

Itoh T., Ishii H. An Approach based on Necessity Measure to the Spanning Tree Problem. J. Oper. Res. Soc. Japan 1996; 39: 247–257p.

Chang P.T., Lee E.S. Ranking Fuzzy Sets Based on the Concept of Existence. Comp. Math. Appl. 1994; 27: 1–21p.

Chang P.T., Lee E.S. Fuzzy Decision Networks and Deconvolution. Comp. Math. Appl. 1999; 37: 53–63p.

Liu B. Theory and Practice of Uncertain Programming. Physica-Verlag, Heidelberg, 2002.

Liu B. Uncertainty Theory: An Introduction to its Axiomatic Foundations. Springer Verlag, Berlin, 2004.

GAO J., Lu M., Fuzzy Quadratic Minimum Spanning Tree Problem. Appl. Math. Comput. 2005; 164: 773–788p.


Refbacks

  • There are currently no refbacks.


This site has been shifted to https://stmcomputers.stmjournals.com/