Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks
Permalink
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 |
| Other contributor: |
Meyer auf der Heide, Friedhelm
Phillips, Cynthia A. |
| Contributor organization: | Helsinki Institute for Information Technology Department of Computer Science |
| Publisher: | ACM |
| Date: | 2010 |
| Language: | eng |
| Number of pages: | 9 |
| Belongs to series: | SPAA’10 |
| ISBN: | 978-1-4503-0079-7 |
| DOI: | https://doi.org/10.1145/1810479.1810533 |
| 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 |
| Peer reviewed: | Yes |
| Usage restriction: | openAccess |
| Self-archived version: | acceptedVersion |
Files in this item
Total number of downloads: Loading...
| Files | Size | Format | View |
|---|---|---|---|
| spaa_2010_paper.pdf | 411.8Kb |
View/ |
This item appears in the following Collection(s)
-
Articles from TUHAT CRIS [50649]