3D Local Algorithm for Dominating Sets of Unit Disk Graphs
Alaa E. Abdallah, T. Fevens and J. Opatrny
A dominating set of a graph G=(V, E) is a subset V ∈ V of the nodes such that for all nodes v ∈ V, either v ∈ V or a neighbor u of v is in V. Several routing protocols in ad hoc networks use a dominating set of the nodes for routing. None of the existing algorithms has a constant approximation factor in a constant number of rounds in 3D. In this paper, we use the nodes’ geometric locations to propose the first local, constant time algorithm that constructs a Dominating Set and Connected Dominating Set of a Unit Disk Graph (UDG) in a 3D environment. Theoretical lower bounds on the size of these sets are given.