The steiner problem in distributed computing systems
The steiner problem in distributed computing systems
复制标题
分布式计算系统中的斯坦纳问题
DOI：
10.1016/0020-0255(93)90128-9
复制
发表时间：
1993
期刊：
影响因子：
--
通讯作者：
M. Kuo
中科院分区：
文献类型：
--
作者：
Gen;Michael E. Houle;M. Kuo
本文提出了一种分布式算法，用于在由加权通信图G=（V，E，c）表示的异步网络中构造近最优Steiner树。所得到的解与任何给定的最小代价Steiner树T min的最坏情况代价比为2（1 - 1 l），其中l是T min的叶子数。该算法的消息复杂度为O（|E| +| V| 1999年，|V| + log| V|）），时间复杂度为O| V| *| V|），其中S是G的要连接的节点的子集。
A distributed algorithm is presented for constructing a nearly optimal Steiner tree in an asynchronous network represented by a weighted communication graph G=(V, E, c). The worst-case cost ratio of the obtained solution to any given minimum-cost Steiner tree T min is 2 (1− 1 l), where l is the number of leaves of T min. The message complexity of the algorithm is O (| E|+| V|∗(| V|+ log| V|)) and the time complexity is O| V|*| V|), where S is the subset of nodes of G to be connected.