2021/11/26 by Vishwanath R. Singireddy, Singireddy, Vishwanath R., Manjanna Basappa +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry (cs.CG) #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2111.13552
openalex publication_date 2021/11/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Given 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. In this paper, we prove that the ev-dominating set problem is \tt NP-hard on unit disk graphs. We also prove that this problem admits a polynomial-time approximation scheme on unit disk graphs. Finally, we give a simple 5-factor linear-time approximation algorithm.