Grandoni, Fabrizio and Könemann, Jochen and Panconesi, Alessandro (2008) Distributed weighted vertex cover via maximal matchings. ACM Transactions on Algorithms, 5 (1). ISSN 1549-6325
Full text not available from this repository.Abstract
In this paper 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(logn+logW^) communication rounds, where W^ is the average vertex-weight. The previous best algorithm for this problem requires O(logn(logn+logW^)) 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
| Item Type: | Scientific journal article, Newspaper article or Magazine article |
|---|---|
| Subjects: | Computer sciences |
| Depositing User: | Fabrizio Grandoni |
| Date Deposited: | 14 Mar 2014 09:05 |
| Last Modified: | 23 May 2016 14:58 |
| URI: | http://repository.supsi.ch/id/eprint/4506 |
Actions (login required)
 |
View Item |