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  -