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

Näytä kaikki kuvailutiedot



Pysyväisosoite

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

Lähdeviite

Å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

Julkaisun nimi: Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks
Tekijä: Åstrand, Matti; Suomela, Jukka
Muu tekijä: Meyer auf der Heide, Friedhelm
Phillips, Cynthia A.
Tekijän organisaatio: Helsinki Institute for Information Technology
Department of Computer Science
Julkaisija: ACM
Päiväys: 2010
Kieli: eng
Sivumäärä: 9
Kuuluu julkaisusarjaan: SPAA’10
ISBN: 978-1-4503-0079-7
DOI-tunniste: https://doi.org/10.1145/1810479.1810533
URI: http://hdl.handle.net/10138/27922
Tiivistelmä: 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.
Avainsanat: 113 Computer and information sciences
Vertaisarvioitu: Kyllä
Pääsyrajoitteet: openAccess
Rinnakkaistallennettu versio: acceptedVersion


Tiedostot

Latausmäärä yhteensä: Ladataan...

Tiedosto(t) Koko Formaatti Näytä
spaa_2010_paper.pdf 411.8KB PDF Avaa tiedosto

Viite kuuluu kokoelmiin:

Näytä kaikki kuvailutiedot