Constant-time distributed dominating set approximation
Fabian Kühn, Rogert Wattenhofer · 2003
Abstract.: Finding a small dominating set is one of the most fundamental problems of classical graph theory. In this paper, we present a new fully distributed approximation algorithm based on LP relaxation techniques. For an arbitrary, possibly constant parameter k and maximum node degree $\\Delta$ , our algorithm computes a dominating set of expected size ${\\rm O}(k\\Delta^{2/k}{\\rm log}(\\Delta)\\vert DS_{\\rm {OPT}}\\vert)$ in ${\\rm O}{(k^2)}$ rounds. Each node has to send ${\\rm O}{(k^2\\Delta)}$ messages of size ${\\rm O}({\\rm log}\\Delta)$ . This is the first algorithm which achieves a non-trivial approximation ratio in a constant number of rounds