Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks
Show simple item record
| dc.contributor.author |
Åstrand, Matti |
|
| dc.contributor.author |
Suomela, Jukka |
|
| dc.contributor.editor |
Meyer auf der Heide, Friedhelm |
|
| dc.contributor.editor |
Phillips, Cynthia A. |
|
| dc.date.accessioned |
2011-10-11T16:00:26Z |
|
| dc.date.available |
2011-10-11T16:00:26Z |
|
| dc.date.issued |
2010 |
|
| dc.identifier.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 |
|
| dc.identifier.citation |
conference |
|
| dc.identifier.other |
PURE: 8445703 |
|
| dc.identifier.other |
PURE UUID: 79f69d67-9043-4f8d-9909-9562e69b8fe1 |
|
| dc.identifier.other |
WOS: 000281485500040 |
|
| dc.identifier.other |
Scopus: 77954929382 |
|
| dc.identifier.uri |
http://hdl.handle.net/10138/27922 |
|
| dc.description.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. |
en |
| dc.format.extent |
9 |
|
| dc.language.iso |
eng |
|
| dc.publisher |
ACM |
|
| dc.relation.ispartof |
SPAA’10 |
|
| dc.relation.isversionof |
978-1-4503-0079-7 |
|
| dc.rights.uri |
info:eu-repo/semantics/openAccess |
|
| dc.subject |
113 Computer and information sciences |
|
| dc.title |
Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks |
en |
| dc.type |
Conference contribution |
|
| dc.contributor.organization |
Helsinki Institute for Information Technology |
|
| dc.contributor.organization |
Department of Computer Science |
|
| dc.description.reviewstatus |
Peer reviewed |
|
| dc.relation.doi |
https://doi.org/10.1145/1810479.1810533 |
|
| dc.rights.accesslevel |
openAccess |
|
| dc.type.version |
acceptedVersion |
|
Files in this item
Total number of downloads: Loading...
This item appears in the following Collection(s)
Show simple item record
