.png){kind=icon}
Return
Improved Distributed Approximate Matching
.png){kind=icon}
PRE
AI
DOI：10.1145/2786753.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
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.
Journal
No journal information available
Organization
No organization information available
Cited Papers
No cited papers available