Singireddy, V.R.Basappa, M.2026-02-062025Lecture Notes in Computer Science, 2025, Vol.15505 LNCS, , p. 39-503029743https://doi.org/10.1007/978-3-031-84543-7_4https://idr.nitk.ac.in/handle/123456789/28716Given an undirected graph G=(V,E), a vertex v∈V is edge-vertex (ev) dominated by an edge e∈E if v is either incident to e or incident to an adjacent edge of e. A set Sev⊆E is an edge-vertex dominating set (referred to as ev-dominating set and in short as EVDS) of G if every vertex of G is ev-dominated by at least one edge of Sev. The minimum cardinality of an ev-dominating set is the ev-domination number. The edge-vertex dominating set problem is to find a minimum ev-domination number. The EVDS problem finds applications in handling security issues in the communication network by identifying a minimum number of critical edges to implement additional security measures to safeguard key components of the network. In this paper, we prove that this problem admits a polynomial-time approximation scheme in unit disk graphs. We also give a simple 5-factor linear-time approximation algorithm. © The Author(s), under exclusive license to Springer Nature Switzerland AG 2025.Approximation algorithmCritical edges in a distributed networkEdge-vertex dominating setUnit disk graph