Distributed Weighted Vertez Cover via Mazimal Matchings
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(log n(log n + log W)) 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.
Fabrizio Grandoni Jochen Konemann Alessandro Panconesi
Dipartimento di Infonnatica, Universita di Roma La Sapienza Via Salaria 113, 00198 Roma, Italy Department of Combinatorics and Optimization, University of Waterloo 200 University Avenue West, Wat
国际会议
The 11th Annual International Computing and Combinatorics Conference COCOON 2005(第11届国际计算和组合会议)
昆明
英文
839-848
2005-08-01（万方平台首次上网日期，不代表论文的发表时间）