Fuzzy Shortest Paths Approximation for Solving the Fuzzy Steiner Tree Problem in Graphs

Authors: Miloš Šeda

Abstract:

In this paper, we deal with the Steiner tree problem (STP) on a graph in which a fuzzy number, instead of a real number, is assigned to each edge. We propose a modification of the shortest paths approximation based on the fuzzy shortest paths (FSP) evaluations. Since a fuzzy min operation using the extension principle leads to nondominated solutions, we propose another approach to solving the FSP using Cheng's centroid point fuzzy ranking method.

Keywords: Steiner tree, single shortest path problem, fuzzyranking, binary heap, priority queue.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1081663

References:

[1] M.R. Berthold and K.-P. Huber, "Constructing Fuzzy Graphs from Examples," Intelligent Data Analysis, vol. 3, pp. 37-53, 1999.
[2] K.R. Bhutani and A. Rosenfeld, "Fuzzy End Nodes in Fuzzy Graphs," Information Sciences, vol. 152, pp. 323-326, 2003.
[3] M. Blue, B. Bush and J. Puckett, "Unified Approach to Fuzzy Graph Problems," Fuzzy Sets and Systems, vol. 125, pp. 355-368, 2002.
[4] A. Boulmakoul, "Generalized Path-Finding Algorithms on Semirings and the Fuzzy Shortest Path Problem," Journal of Computational and Applied Mathematics, vol. 162, pp. 263-272, 2004.
[5] P. Bosc and J. Kacprzyk (eds.), Fuzziness in Database Management Systems. Heidelberg: Physica-Verlag, 1995.
[6] D. Cavendish, A. Fei, M. Gerla and R. Rom, "On the Construction of Low Cost Multicast Trees with Bandwidth Reservation," in Proc. of the Int. Conf. on High-Performance Computing and Networking HPCN, Amsterdam, 1998, 29 pp.
[7] S. Chanas and P. Zielinski, "Ranking Fuzzy Interval Numbers in the Setting of Random Sets - Further Results," Information Sciences, vol. 117, pp. 191-2000, 1999.
[8] P.-T. Chang, and E.S. Lee, "Fuzzy Arithmetics and Comparison of Fuzzy Numbers", in M. Delgado, J. Kacprzyk, J.-L. Verdegay and M.A. Vila (eds.), Fuzzy Optimization. Heidelberg: Physica-Verlag, pp. 69-82, 1994.
[9] C.-H. Cheng, "A New Approach for Ranking Fuzzy Numbers by Distance Method," Fuzzy Sets and Systems, vol. 95, pp. 307-317, 1998.
[10] T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithms. Massachusetts: MIT Press, 2001.
[11] D.W. Corne, M.J. Oates and G.D. Smith (eds.), Telecommunications Optimization: Heuristic and Adaptive Techniques. New York: John Wiley & Sons, 2000.
[12] D.-Z. Du, J.M. Smith, and J.H. Rubinstein, Advances in Steiner Trees. Dordrecht: Kluwer Academic Publishers, 2000.
[13] A. Fink, G. Schneidereit, G. and S. Voss, "Solving General Ring Network Design Problems by Meta-Heuristics," in M. Laguna and J.L. González Velarde (eds.), Computing Tools for Modeling, Optimization and Simulation Interfaces in Computer Science and Operations Research. Boston: Kluwer Academic Publishers, pp. 91-113, 1999.
[14] P. Fortemps and M. Roubens, "Ranking and Defuzzification Methods Based on Area Compensation," Fuzzy Sets and Systems, vol. 82, pp. 319-330, 1996.
[15] J. Gross and J. Yellen, Graph Theory and Its Applications. Boca Raton: CRC Press, 1999.
[16] P. Grzegorzewski, "Metrics and Orders in Space of Fuzzy Numbers," Fuzzy Sets and Systems, vol. 97, pp. 83-94, 1998.
[17] F.K. Hwang, D.S. Richards and P. Winter, The Steiner Tree Problem. Amsterdam: North-Holland, 1992.
[18] S. Khuller, "Design and Analysis of Algorithms," Lecture Notes, University of Maryland, Department of Computer Science, 1994, 112 pp.
[19] M. Modarres and S. Sadi-Nezhad, "Ranking Fuzzy Numbers by Preference Ratio," Fuzzy Sets and Systems, vol. 118, pp. 429-436, 2001.
[20] D.M. Mount, "Design and Analysis of Computer Algorithms," Lecture Notes, University of Maryland, College Park, 1999, 131 pp.
[21] T. Sav┼íek, M. Vezjak and N. Pave┼íić, "Fuzzy Trees in Decision Support Systems," European Journal of Operational Research, 2006, in print.
[22] A. Sengupta and T.K. Pal, "On Comparing Interval Numbers," European Journal of Operational Research, vol. 127, pp. 28-43, 2000.
[23] S. Tan, Y. Yu and P.-Z. Wang,, "Building Fuzzy Graphs form Samples of Nonlinear Functions," Fuzzy Sets and Systems, vol. 93, pp. 337-352, 1998.
[24] X. Wang and E.E. Kerre, "Reasonable Properties for Ordering of Fuzzy Quantities (I)," Fuzzy Sets and Systems, vol. 118, pp. 375-385, 2001.
[25] X. Wang and E.E. Kerre, "Reasonable Properties for Ordering of Fuzzy Quantities (II)," Fuzzy Sets and Systems, vol. 118, pp. 387-405, 2001.
[26] J.-S. Yao and K. Wu, "Ranking Fuzzy Numbers Based on Decomposition Principle and Signed Distance," Fuzzy Sets and Systems, vol. 116, pp. 275-288, 2000.
[27] L.A. Zadeh, "Fuzzy Logic and the Calculi of Fuzzy Rules, Fuzzy Graphs, Fuzzy Probabilities," Computers & Mathematics with Applications, vol. 37, p. 35, 1999.