Distributed Weighted Matching
Distributed Weighted Matching
复制标题
DOI：
10.1007/978-3-540-30186-8_24
复制
发表时间：
2004-10
期刊：
影响因子：
--
通讯作者：
Mirjam Wattenhofer;Roger Wattenhofer
中科院分区：
文献类型：
--
作者：
Mirjam Wattenhofer;Roger Wattenhofer
在这篇文章中，我们提出了快速和完全分布式的加权树和一般加权图的匹配算法。树算法的时间复杂度和逼近比都是恒定的。特别地，逼近比为4。对于一般的图算法，我们证明了该算法的常数比界为5，多对数时间复杂度为O(Log2n)。
In this paper, we present fast and fully distributed algorithms for matching in weighted trees and general weighted graphs. The time complexity as well as the approximation ratio of the tree algorithm is constant. In particular, the approximation ratio is 4. For the general graph algorithm we prove a constant ratio bound of 5 and a polylogarithmic time complexity ofO(log2n).