Covering problem on fuzzy graphs and its application in disaster management system
- PDF / 705,276 Bytes
- 13 Pages / 595.276 x 790.866 pts Page_size
- 16 Downloads / 206 Views
METHODOLOGIES AND APPLICATION
Covering problem on fuzzy graphs and its application in disaster management system Sonia Mandal1
· Nupur Patra2 · Madhumangal Pal1
© Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract Nowadays the fuzzy graphs gained popularity due to their wide applications in different areas of science, engineering, social sciences, etc.In this paper, we consider covering problem in fuzzy graph. Different types of covering problems have been defined in this paper. Almost all problems are new. For each of these problems separate study is required. Also, the covering set, strong covering set, minimal covering set, etc., are defined and explained with examples. In a graph, each vertex can cover only those vertices that lie within its covering radius along shortest path and no vertex can cover itself. Here, an algorithm is designed to find the different types of covering sets on a fuzzy graph. An imprecise number, instead of a real number, namely interval number and triangular fuzzy number are considered as arc length of a fuzzy graph. To the best of our knowledge no works are available for covering problem on fuzzy graphs/networks. An application of covering set in natural disaster management is discussed to highlight the importance of the covering problem. In this application, an algorithm is designed to find all the facility vertices (or supply vertices) for given vertex and covering radius. Keywords Fuzzy graph · Fuzzy paths · Covering set · Strong covering set · Facility location problem
1 Introduction Set covering problem (SCP) is a very important topic in network optimization known as combinatorial optimization. Set covering problem has received special attention due to the huge evolution of mobile communication, social networks such as Facebook, ResearchGate, Twitter, LinkedIn along with the different types of applications built on them. Graph network used in modern applications starting from mobile communication to VLSI design is identified to be highly dynamic structures, changing at high rates. Another feature Communicated by V. Loia.
B
Sonia Mandal [email protected] Nupur Patra [email protected] Madhumangal Pal [email protected]
1
Department of Applied Mathematics with Oceanology and Computer Programming, Vidyasagar University, Midnapore 721 102, India
2
Department of Mathematics, Raja N. L. Khan Women’s College, Gope Palace, Midnapore 721102, India
of networks that has recently gained attention by researchers in recent years is their social nature. In many applications a network is constructed by a set of users that want to maximize their individual profit. The vertex covering is one of the widely studied problem in graph theory as it is used to solve facility location problem and many other problems in operations research particularly in transportation problem. A vertex cover of a graph is a set of vertices such that each edge of the graph is incident to at least one vertex of the set. Obviously, the set of all vertices of the given graph is a verte
Data Loading...
