Vertex covering problems of fuzzy graphs and their application in CCTV installation
- PDF / 1,811,724 Bytes
- 24 Pages / 595.276 x 790.866 pts Page_size
- 98 Downloads / 182 Views
(0123456789().,-volV)(0123456789(). ,- volV)
ORIGINAL ARTICLE
Vertex covering problems of fuzzy graphs and their application in CCTV installation Anushree Bhattacharya1 • Madhumangal Pal1 Received: 31 March 2020 / Accepted: 2 September 2020 Ó Springer-Verlag London Ltd., part of Springer Nature 2020
Abstract In graph theory, a vertex covering set VC is a set of vertices such that each edge of the graph is incident to at least one of the vertices of the set VC . The problems related to vertex covering are called vertex covering problems. Many real-life problems contain a lot of uncertainties. To handle such uncertainties, concept of fuzzy set/graph is used. Here, we consider the covering problems of fuzzy graph to model some real-life problems. In this paper, a vertex covering problem is modeled as a series of linear and nonlinear programming problems with the help of basic graph-theoretic concept. In this model, the following objectives are considered: (1) the total number of facilities, the coverage area and total efficiency of all facilities are maximized, whereas (2) the total cost for the covering problem is minimized. Some new sets are defined and determined to make best decision on the basis of the features of facilities of the fuzzy system. An illustration is given to describe the whole model. Application of the said vertex covering problem to make a suitable decision for the placement of CCTVs in a city with the help of the developed formulations is given in a systematic way. To find the solutions, some algorithms are designed and the mathematical software ‘LINGO’ is used to keep the fuzziness of the parameters involved in the problems. Keywords Graph theory Fuzzy graph Fuzzy number Covering problem Fuzzy optimization
1 Introduction The past decades have witnessed an explosive growth in the literature on location problems. Location is considered to be one of the more profitable areas of applied operations research, which is a part of applied mathematics. Not only operations researchers but economists, urban planners, architects, regional scientists and engineers revealed a great interest in location problems. In a broad sense, the location problems are to be used in solving some covering problems by locating or placing facility points; a region can be covered up easily. Also, there are some real-life
& Madhumangal Pal [email protected] Anushree Bhattacharya [email protected] 1
Department of Applied Mathematics with Oceanology and Computer Programming, Vidyasagar University, Midnapore 721 102, India
problems which are the mixture of location problems and covering problems. In some covering problems, a customer should be served by at least one facility within a given critical distance (not necessarily the nearest facility). In most of the covering problems, customers receive services from facilities depending on the distance between the customer and facilities. A customer can receive service from a facility if the distance between the customer and facility is equal to or less than
Data Loading...
