Fulltext

Constant-time distributed dominating set approximation

Kuhn, Fabian ; Wattenhofer, Roger

In: Distributed Computing, 2005, vol. 17, no. 4, p. 303-310

Add to personal list
    Title
    • Constant-time distributed dominating set approximation
    Author
    • Kuhn, Fabian. Computer Engineering and Networks Laboratory, ETH Zürich, 8092, Zürich, Switzerland
    • Wattenhofer, Roger. Computer Engineering and Networks Laboratory, ETH Zürich, 8092, Zürich, Switzerland
    Document Type
    • Postprint
    Classification
    • Computer science
    OAI-PMH Identifier
    • oai:doc.rero.ch:318691
    Summary
    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