Anzeige
Erschienen in:
2007 | OriginalPaper | Buchkapitel
A Faster Distributed Approximation Scheme for the Connected Dominating Set Problem for Growth-Bounded Graphs
verfasst von : Beat Gfeller, Elias Vicari
Erschienen in: Ad-Hoc, Mobile, and Wireless Networks
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We present a distributed algorithm for finding a (1 +
ε
)-approximation of a
Minimum Connected Dominating Set
in the class of
Growth-Bounded graphs
, which includes
Unit Disk graphs
. In addition, the computed Connected Dominating Set guarantees a constant stretch factor on the length of a shortest path with respect to the original graph and induces a subgraph of constant degree. The nodes do not require any positioning or distance information.
The algorithm runs in
$O\big(T_{\texttt {MIS}} + 1/\epsilon^{O(1)}\log (1/\epsilon)\log^* n\big)$
synchronous rounds, where
$T_{\texttt {MIS}}$
is the time for computing a Maximal Independent Set (
MIS
) in the network graph. Using the fastest known deterministic algorithm for computing a
MIS
, the total running time is
$O\big( (\log\Delta+ 1/\epsilon^{O(1)}) \cdot \log^* n \big)$
, where
Δ
is the maximum degree of the network graph. If one allows randomization, the running time reduces to
$O\big((\log\log n + 1/\epsilon^{O(1)})\cdot \log^* n \big)$
rounds.