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.
approximation algorithms; distributed algorithms; maximal matching; vertex cover
01 Pubblicazione su rivista::01a Articolo in rivista
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]
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/362014
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 30
  • ???jsp.display-item.citation.isi??? 17
social impact