Approximation Algorithms for Emergency Vertex Cover with Few Stations and Fault-Tolerant Coverage

Quanlong Niu, Riheng Jia

The Emergency Vertex Cover problem (Em-VC) assigns budgets to stations at graph vertices to cover every edge while minimizing the total budget. The cost of covering an edge from a…