TY -
T1 - Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks
SN - /
UR - http://hdl.handle.net/10138/27922
T3 -
A1 - Åstrand, Matti; Suomela, Jukka
A2 - Meyer auf der Heide, Friedhelm; Phillips, Cynthia A.
PB - ACM
Y1 - 2010
LA - eng
AB - We present a distributed algorithm that finds a maximal edge packing in O(Δ + log* W) synchronous communication rounds in a weighted graph, independent of the number of nodes in the network; here Δ is the maximum degree of the graph and W is the maximum weight. As a direct application, we have a distributed 2-approximation algorithm for minimum-weight vertex cover, with the same running time. We also show how to find an f-approximation of minimum-weight set cover in O(f2k2 + fk log* W) rounds; h...
VO -
IS -
SP -
OP -
KW - 113 Computer and information sciences
N1 -
PP -
ER -