Title :
Distributed dominating sets on grids
Author :
Fata, Elaheh ; Smith, Stephen L. ; Sundaram, Suresh
Author_Institution :
Dept. of Electr. & Comput. Eng., Univ. of Waterloo, Waterloo, ON, Canada
Abstract :
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 lprovided by this centralized algorithm is upper-bounded by ⌈(m+2)(n+2) over 5⌉ 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.
Keywords :
distributed algorithms; graph theory; set theory; centralized algorithm; distributed algorithm; distributed dominating sets; grid graph; grid vertices; k-distance dominating set problem; near optimal dominating sets; optimal domination number; Algorithm design and analysis; Clustering algorithms; Distributed algorithms; Greedy algorithms; Manganese; Robot sensing systems;
Conference_Titel :
American Control Conference (ACC), 2013
Conference_Location :
Washington, DC
Print_ISBN :
978-1-4799-0177-7
DOI :
10.1109/ACC.2013.6579839
