Improved distributed steiner forest construction
Improved distributed steiner forest construction
复制标题
改进分布式斯坦纳森林建设
DOI：
10.1145/2611462.2611464
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Boaz Patt-Shamir
中科院分区：
文献类型：
--
作者：
Christoph Lenzen;Boaz Patt-Shamir
我们提出了在CONGEST模型中构建Steiner森林的新分布式算法。我们的确定性算法发现，对于任何给定的常数ε>0，一个（2+ε）-近似在~O（sk+<${min（st，n）}）轮，其中s是最短路径直径，t是终端的数量，k是终端组件的数量在输入中，和n是节点的数量。我们的随机算法以很高的概率在时间~O（k+min（s，n）+D）中找到O（log n）-近似，其中D是网络的未加权直径。我们还证明了Steiner森林问题的任何分布式近似算法的运行时间的匹配下界~Ω（k+min（s，n）+D）。以前的算法都是随机的，要么在O（sk）时间内得到O（log n）-近似，要么在O（（n+t）1+ε+D）时间内得到O（1/ε）-近似.
We present new distributed algorithms for constructing a Steiner Forest in the CONGEST model. Our deterministic algorithm finds, for any given constant ε>0, a (2+ε)-approximation in ~O(sk+√{min(st,n)}) rounds, where s is the shortest path diameter, t is the number of terminals, k is the number of terminal components in the input, and n is the number of nodes. Our randomized algorithm finds, with high probability, an O(log n)-approximation in time ~O(k+min(s,√ n)+D), where D is the unweighted diameter of the network. We also prove a matching lower bound of ~Ω(k+min(s,√n)+D) on the running time of any distributed approximation algorithm for the Steiner Forest problem. Previous algorithms were randomized, and obtained either an O(log n)-approximation in ~O(sk) time, or an O(1/ε)-approximation in O((√n+t)1+ε+D) time.
登录
查看更多内容
DOI：
10.1145/2488608.2488656
发表时间：
2012-10
期刊：
--
影响因子：
--
作者：
C. Lenzen;B. Patt-Shamir
通讯作者：
C. Lenzen;B. Patt-Shamir
DOI：
10.1145/103418.103437
发表时间：
1991-01
期刊：
SIAM J. Comput.
影响因子：
--
作者：
Exa Corporation;Brown University;University of California-Davis
通讯作者：
Exa Corporation;Brown University;University of California-Davis
影响因子：
1.3
作者：
Maleq Khan;F. Kuhn;D. Malkhi;Gopal Pandurangan;Kunal Talwar
通讯作者：
Kunal Talwar
小型 k 支配集的快速分布式构建及应用
DOI：
--
发表时间：
1998
期刊：
J. Algorithms
影响因子：
--
作者：
S. Kutten;D. Peleg
通讯作者：
D. Peleg
分布式 MST 构建时间复杂度的近紧下界
DOI：
10.1109/sffcs.1999.814597
发表时间：
1999
期刊：
40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039)
影响因子：
--
作者：
D. Peleg;Vitaly Rubinovich
通讯作者：
Vitaly Rubinovich