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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 588-607 |
| Number of pages | 20 |
| Journal | Journal of Discrete Algorithms |
| Volume | 4 |
| Issue number | 4 |
| DOIs | |
| State | Published - Dec 2006 |
Keywords
- Approximation algorithms
- Distributed algorithms
- Maximum-weight matching
- Minimum-weight dominating set
- Minimum-weight independent set
ASJC Scopus subject areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics