In this article, we consider the problem of computing a minimum-weight vertex-cover in an n-node, weighted, undirected graph G = (V,E). We present a fully distributed algorithm for computing vertex covers of weight at most twice the optimum, in the case of integer weights. Our algorithm runs in an expected number of O(log n + log Ŵ) communication rounds, where Ŵ is the average vertex-weight. The previous best algorithm for this problem requires O(log n(log n + logŴ)) rounds and it is not fully distributed. For a maximal matching M in G, it is a well-known fact that any vertex-cover in G needs to have at least M vertices. Our algorithm is based on a generalization of this combinatorial lower-bound to the weighted setting. © 2008 ACM.
Distributed weighted vertex cover via maximal matchings / Grandoni, Fabrizio; Jochen, Konemann; Panconesi, Alessandro. - In: ACM TRANSACTIONS ON ALGORITHMS. - ISSN 1549-6325. - 5:1(2008), pp. 1-12. [10.1145/1435375.1435381]
Distributed weighted vertex cover via maximal matchings
GRANDONI, FABRIZIO;PANCONESI, Alessandro
2008
Abstract
In this article, we consider the problem of computing a minimum-weight vertex-cover in an n-node, weighted, undirected graph G = (V,E). We present a fully distributed algorithm for computing vertex covers of weight at most twice the optimum, in the case of integer weights. Our algorithm runs in an expected number of O(log n + log Ŵ) communication rounds, where Ŵ is the average vertex-weight. The previous best algorithm for this problem requires O(log n(log n + logŴ)) rounds and it is not fully distributed. For a maximal matching M in G, it is a well-known fact that any vertex-cover in G needs to have at least M vertices. Our algorithm is based on a generalization of this combinatorial lower-bound to the weighted setting. © 2008 ACM.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
