Autor: |
Azar, Yossi, Erlebach, Thomas, Czygrinow, Andrzej, Hańćkowiak, Michał |
Zdroj: |
Algorithms - ESA 2006; 2006, p244-255, 12p |
Abstrakt: |
We give efficient deterministic distributed algorithms which given a graph G from a proper minor-closed family $\mathcal{C}$ find an approximation of a minimum dominating set in G and a minimum connected dominating set in G. The algorithms are deterministic and run in a poly-logarithmic number of rounds. The approximation accomplished differs from an optimal by a multiplicative factor of (1+o(1)). [ABSTRACT FROM AUTHOR] |
Databáze: |
Complementary Index |
Externí odkaz: |
|