Facility Location: A Theoretical Approach for Flood Relief - Gurusamy, Vairaprakash; Nandhini, K (International Journal of Computer Sciences and Engineering, 2025)
We present a theoretical approach to come up with an effective mechanism for flood relief in terms of facility location problem with certain constraints. Facility location problem is a well studied economical decision problem to locate limited facility on demand points to cover maximum demand. Let consider a facility network under link failure. The problem is to locate emergency response facilities on a network with links that are subject to a failure model, called vulnerability − based dependency. We address the MAX-EXP-COVER-R problem in the facility network subjects to VB-dependency failure model. The MAX-EXP-COVER-R problem is known to be NP-hard. Let the distance factor R is relaxed from MAX-EXP-COVER-R problem, then it becomes MAX-EXP-COVER problem. The MAX-EXP-COVER problem can be solved in linear time using greedy algorithm. The MAX-EXP-COVER problem is further reduced into an instance of full binary tree, and then run MAX-WT-K-LEAF-SUBTREE problem on the tree will outputs the solution for MAX-EXP-COVER problem. Let the distance factor R = 1, then MAX-EXP-COVER-R problem is equivalent to budgeted dominating set problem with budget k and the induced subgraph of the solution set is need not to be connected.