Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks

Show full item record



Permalink

http://hdl.handle.net/10138/27922

Citation

Åstrand , M & Suomela , J 2010 , Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks . in F Meyer auf der Heide & C A Phillips (eds) , SPAA’10 : Proceedings of the Twenty-Second Annual Symposium on Parallelism in Algorithms and Architectures, June 13–15, 2010. Thira, Santorini, Greece . ACM , pp. 294–302 , ACM Symposium on Parallelism in Algorithms and Architectures (SPAA) , Santorini , Greece , 13/06/2010 . https://doi.org/10.1145/1810479.1810533

Title: Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks
Author: Åstrand, Matti; Suomela, Jukka
Editor: Meyer auf der Heide, Friedhelm; Phillips, Cynthia A.
Contributor: University of Helsinki, Helsinki Institute for Information Technology
Publisher: ACM
Date: 2010
Language: eng
Number of pages: 9
Belongs to series: SPAA’10 Proceedings of the Twenty-Second Annual Symposium on Parallelism in Algorithms and Architectures, June 13–15, 2010. Thira, Santorini, Greece
ISBN: 978-1-4503-0079-7
URI: http://hdl.handle.net/10138/27922
Abstract: 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; here k is the maximum size of a subset in the set cover instance, f is the maximum frequency of an element, and W is the maximum weight of a subset. The algorithms are deterministic, and they can be applied in anonymous networks.
Subject: 113 Computer and information sciences
Rights:


Files in this item

Total number of downloads: Loading...

Files Size Format View
spaa_2010_paper.pdf 411.8Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record