An efficient distributed algorithm for constructing small dominating sets

Lujun Jia, Rajmohan Rajaraman, Torsten Suel

    Research output: Contribution to journalArticle

    Abstract

    The dominating set problem asks for a small subset D of nodes in a graph such that every node is either in D or adjacent to a node in D. This problem arises in a number of distributed network applications, where it is important to locate a small number of centers in the network such that every node is nearby at least one center. Finding a dominating set of minimum size is NP-complete, and the best known approximation is logarithmic in the maximum degree of the graph and is provided by the same simple greedy approach that gives the well-known logarithmic approximation result for the closely related set cover problem. We describe and analyze new randomized distributed algorithms for the dominating set problem that run in polylogarithmic time, independent of the diameter of the network, and that return a dominating set of size within a logarithmic factor from optimal, with high probability. In particular, our best algorithm runs in O(log n log Δ) rounds with high probability, where n is the number of nodes, Δ is one plus the maximum degree of any node, and each round involves a constant number of message exchanges among any two neighbors; the size of the dominating set obtained is within O(log Δ) of the optimal in expectation and within O(log n) of the optimal with high probability. We also describe generalizations to the weighted case and the case of multiple covering requirements.

    Original languageEnglish (US)
    Pages (from-to)193-205
    Number of pages13
    JournalDistributed Computing
    Volume15
    Issue number4
    DOIs
    StatePublished - Dec 2002

    Keywords

    • Ad hoc network
    • Approximation algorithm
    • Distributed computing
    • Dominating set

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Hardware and Architecture
    • Computer Networks and Communications
    • Computational Theory and Mathematics

    Fingerprint Dive into the research topics of 'An efficient distributed algorithm for constructing small dominating sets'. Together they form a unique fingerprint.

  • Cite this