Finding a small dominating set is one of the most fundamental problems of traditional graph theory. In this paper, we present a new fully distributed approximation algorithm based on LP relaxation techniques. For an arbitrary parameter k and maximum degree A, our algorithm computes a dominating set of expected size O(kA 2/k log AIDSoPTI) in O(k 2) rounds where each node has to send O(k2A) messages of size O(logA). This is the first algorithm which achieves a non-trivial approximation ratio in a constant number of rounds.
Recently, Kuhn and Wattenhofer REF proposed a new distributed MDS approximation algorithm based on linear programming (LP) relaxation techniques.
Constant-time distributed dominating set approximation
PODC '03
Computer Science