Approximability of Edge-Vertex Domination in Unit Disk Graphs
摘要
Given an undirected graph \(G=(V,E)\) , a vertex \(v\in V\) is edge-vertex (ev) dominated by an edge \(e\in E\) if v is either incident to e or incident to an adjacent edge of e. A set \(S^{ev}\subseteq 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 \(S^{ev}\) . 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.