Affordable Access

Publisher Website

Distributed algorithms for weighted problems in sparse graphs

Authors
Journal
Journal of Discrete Algorithms
1570-8667
Publisher
Elsevier
Publication Date
Volume
4
Issue
4
Identifiers
DOI: 10.1016/j.jda.2005.07.006
Keywords
  • Distributed Algorithms
  • Approximation Algorithms
  • Maximum-Weight Matching
  • Minimum-Weight Dominating Set
  • Minimum-Weight Independent Set
Disciplines
  • Computer Science

Abstract

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.

There are no comments yet on this publication. Be the first to share your thoughts.