Distributed Approximation Algorithms in Unit-Disk Graphs

摘要

We will give distributed approximation schemes for the maximum matching problem and the minimum connected dominating set problem in unit-disk graphs. The algorithms are deterministic, run in a poly-logarithmic number of rounds in the message passing model and the approximation error can be made O(1/log~κ |G|) where |G| is the order of the graph and κ is a positive integer.