Fuzzy spanners

  • Authors

    • Mohammad Farshi Yazd University
    2014-12-06
    https://doi.org/10.14419/jacst.v3i2.3800
  • Networks, Graphs, Fuzzy Spanners, Greedy Algorithm, Fuzzy Weighted Graphs.

  • Abstract

    Graphs have wide applications in variety of applications, especially network analysis. Spanners give a sparse approximation of any graph as well as complete graph, which has wide applications so far. Because of its applications, graph definitions generalized to fuzzy sets and fuzzy weighted graph defined and studied vastly in past and has applications in several fields. In this paper, we define spanners for fuzzy weighted graphs and well as points come from a fuzzy metric space. We propose some algorithm to compute such a spanner. Finally, we pose some open problem that can be considered for future works.

  • References

    1. I. Althofer, G. Das, D. P. Dobkin, D. Joseph, and J. Soares. On sparse spanners of weighted graphs. Discrete and Computational Geometry, 9(1), (1993), pp. 81--100.
    2. P. B. Callahan and S. R. Kosaraju. A decomposition of multidimensional point sets with applications to k-nearestneighbors and n-body potential _elds. Journal of the ACM, 42, (1995), 67--90.
    3. C. Cornelis, P. De Kesel, and E. E. Kerre. Shortest paths in fuzzy weighted graphs. International Journal of Intelligent Systems, 19(11), (2004), 1051--1068.
    4. P. Diamond and P. Kloeden. Metric Spaces of Fuzzy Sets: Theory and Applications. World Scientific, (1994).
    5. D. Dubois and H. Prade. Fuzzy sets and systems - Theory and applications. Academic press, New York, (1980).
    6. M. Farshi and J. Gudmundsson. Experimental study of geometric t-spanners. Journal of Experimental Algorithmics, 14:3, (2010), 1.3--3:1.39.
    7. P. Jayagowri and G. Geetharamani. Various approaches for solving the network problems using tlr intuitionistic fuzzy numbers. International Journal of Computer Applications, Vol. 63, No. 20, (2013), pp. 7--13.
    8. M. Karunambigai, P. Rangasamy, K. Atanassov, and N. Palaniappan. An intuitionistic fuzzy graph method for finding the shortest paths in networks. In Theoretical Advances and Applications of Fuzzy Logic and Soft Computing, volume 42 of Advances in Soft Computing, (2007), pp. 3--10.
    9. C. M. Klein. Fuzzy shortest paths. Fuzzy Sets and Systems, Vol. 39, No. 1, (1991), pp. 27 -- 41.
    10. J.-Y. Kung and T.-N. Chuang. The shortest path problem with discrete fuzzy arc lengths. Computers & Mathematics with Applications, Vol. 49, No. 23, (2005), pp. 263 – 270.
    11. X.-Y. Li. Applications of computational geometry in wireless ad hoc networks. In X.-Z. Cheng, X. Huang, and D.-Z. Du, editors, Ad Hoc Wireless Networking. Kluwer, (2003).
    12. G. Narasimhan and M. Smid. Geometric spanner networks. Cambridge University Press, (2007).
    13. G. Navarro and R. Paredes. Practical construction of metric t-spanners. In ALENEX'03: Proceedings of the 5th Workshop on Algorithm Engineering and Experiments, (2003), pp. 69--81.
    14. S. Okada and T. Soper. A shortest path problem on a network with fuzzy arc lengths. Fuzzy Sets and Systems, Vol. 109, No. 1, (2000), pp. 129 -- 140.
    15. B. A. Siddhartha Sankar Biswas and M. N. Doja. An algorithm for extracting intuitionistic fuzzy shortest path in a graph. Applied Computational Intelligence and Soft Computing, (2013).
    16. M. Sigurd and M. Zachariasen. Construction of minimum-weight spanners. In ESA'04: Proceedings of the 12th Annual European Symposium on Algorithms, volume 3221 of Lecture Notes in Computer Science. Springer-Verlag, (2004).
    17. A. Tajdin, I. Mahdavi, N. Mahdavi-Amiri, B. S. Gildeh, and R. Hassanzadeh. A novel approach for finding a shortest path in a mixed fuzzy network. Wireless Sensor Network, Vol. 2, No. 2, (2010), pp. 148--160.

  • Downloads

  • How to Cite

    Farshi, M. (2014). Fuzzy spanners. Journal of Advanced Computer Science & Technology (JACST), 3(2), 249-252. https://doi.org/10.14419/jacst.v3i2.3800

    Received date: 2014-11-04

    Accepted date: 2014-12-03

    Published date: 2014-12-06