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

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.

Authors:

• Miloš Šeda

Keywords:

• Steiner tree
• single shortest path problem
• fuzzyranking
• binary heap
• priority queue.

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.