Motivated by routing issues in ad hoc networks, we present polylogarithmic-time distributed algorithms for two problems. Given a network, we first show how to compute connected and weakly connected dominating sets whose size is at most O(logΔ) times optimal, Δ being the maximum degree of the input network. This is best-possible if NP ⊈ DTIME[nO(log log n)] and if the processors are limited to polynomial-time computation. We then show how to construct dominating sets which satisfy the above properties, as well as the "low stretch" property that any two adjacent nodes in the network have their dominators at a distance of at most O(log n) in the network. (Given a dominating set S, a dominator of a vertex u is any v ∊ S such that the distance between u and v is at most one.) We also show our time bounds to be essentially optimal.
展开▼
机译：受ad hoc网络中路由问题的影响，我们提出了针对两个问题的多对数时间分布式算法。给定一个网络，我们首先展示如何计算大小最大为最佳的（I> O （logΔ）乘以Δ是输入网络的最大程度的连通和弱连通的支配集。如果NP⊈D TIME [ n O （对数日志 n ）< / SUP>]，以及处理器是否限于多项式时间计算。然后，我们展示如何构造满足上述属性的控制集，以及网络中任何两个相邻节点的控制者在最多 O （log网络中的 n ）。 （给定控制集 S ，顶点 u 的控制者是任何 v ∊ S 使得距离在 u 和 v 之间最多是一个。）我们还证明了我们的时间范围本质上是最佳的。
展开▼
