Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
431761 | Journal of Discrete Algorithms | 2006 | 20 Pages |
Abstract
We study distributed algorithms for three graph-theoretic problems in weighted trees and weighted planar graphs. For trees, we present an efficient deterministic distributed algorithm which finds an almost exact approximation of a maximum-weight matching. In addition, in the case of trees, we show how to approximately solve the minimum-weight dominating set problem. For planar graphs, we present an almost exact approximation for the maximum-weight independent set problem.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
A. Czygrinow, M. Hańćkowiak,