Journal
ACM TRANSACTIONS ON ALGORITHMS
Volume 5, Issue 1, Pages -Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/1435375.1435381
Keywords
Approximation algorithms; distributed algorithms; maximal matching; vertex cover
Ask authors/readers for more resources
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 (W) over cap) communication rounds, where (W) over cap is the average vertex-weight. The previous best algorithm for this problem requires O(log n(log n+ log (W) over cap)) 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 vertical bar M vertical bar vertices. Our algorithm is based on a generalization of this combinatorial lower-bound to the weighted setting.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available