2013/03/14 by Elaheh Fata, Fata, Elaheh, Stephen L. Smith +3
Computer Science · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Distributed systems and fault tolerance #FOS: Computer and information sciences #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1303.3564
openalex publication_date 2013/03/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper presents a distributed algorithm for finding near optimal dominating sets on grids. The basis for this algorithm is an existing centralized algorithm that constructs dominating sets on grids. The size of the dominating set provided by this centralized algorithm is upper-bounded by \lceil((m+2)(n+2))/(5)\rceil for m× n grids and its difference from the optimal domination number of the grid is upper-bounded by five. Both the centralized and distributed algorithms are generalized for the k-distance dominating set problem, where all grid vertices are within distance k of the vertices in the dominating set.