Advertisement
Published in:
2006 | OriginalPaper | Chapter
Distributed Almost Exact Approximations for Minor-Closed Families
Authors : Andrzej Czygrinow, Michał Hańćkowiak
Published in: Algorithms – ESA 2006
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. 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)).