Constant-time distributed dominating set approximation |
| |
Authors: | Fabian Kuhn Roger Wattenhofer |
| |
Affiliation: | (1) Computer Engineering and Networks Laboratory, ETH Zürich, 8092 Zürich, Switzerland |
| |
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
, our algorithm computes a dominating set of expected size
in
rounds. Each node has to send
messages of size
. This is the first algorithm which achieves a non-trivial approximation ratio in a constant number of rounds.Received: 9 September 2003, Accepted: 2 September 2004, Published online: 13 January 2005The work presented in this paper was supported (in part) by the National Competence Center in Research on Mobile Information and Communication Systems (NCCR-MICS), a center supported by the Swiss National Science Foundation under grant number 5005-67322. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|