.png){kind=icon}
返回
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
.png){kind=icon}
摘要
En 中文
We present distributed network algorithms to compute weighted and unweighted matchings with improved approximation ratios and running times. The computational model is a network of processors exchanging
O
(log
n
)-bit messages (the CONGEST model). For unweighted graphs, we give an algorithm providing (1-ϵ)-approximation in
O
(log
n
) time for any constant ϵ>0, improving on the classical ½-approximation in
O
log
n
) time of Israeli and Itai [1986]. The time complexity of the algorithm depends on 1⁃ϵ exponentially in the general case, and polynomially in bipartite graphs. For weighted graphs, we present another algorithm which provides (½-ϵ) approximation in general graphs in
O
(logϵ
-1
log
n
) time, improving on the previously known algorithms which attain (¼-ϵ)-approximation in
O
(log
n
) time or ½-approximation in
O
(
n
) time. All our algorithms are randomized: the complexity bounds hold both with high probability and for the expected running time.
期刊
暂无期刊信息
机构
暂无机构信息
引用论文
暂无论文信息