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...

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

This item appears in the following Collection(s)

Show simple item record