Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Distributed Almost Exact Approximations for Minor-Closed Families
verfasst von : Andrzej Czygrinow, Michał Hańćkowiak
Erschienen in: Algorithms – ESA 2006
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 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)).