Distributed algorithms for weighted problems in sparse graphs

DOI10.1016/j.jda.2005.07.006zbMath1109.68132OpenAlexW1979561519MaRDI QIDQ866546

Andrzej Czygrinow, Michał Hanćkowiak

Publication date: 14 February 2007

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2005.07.006

zbMATH Keywords

approximation algorithmsdistributed algorithmsminimum-weight dominating setmaximum-weight matchingminimum-weight independent set

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15)

Related Items (3)

The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs ⋮ A new distributed approximation algorithm for the maximum weight independent set problem ⋮ Fast Distributed Approximations in Planar Graphs

Cites Work

• Distributed algorithm for approximating the maximum matching
• Distributed Algorithm for Better Approximation of the Maximum Matching
• Deterministic coin tossing with applications to optimal parallel list ranking
• Locality in Distributed Graph Algorithms
• An efficient distributed algorithm for constructing small dominating sets
• Fast distributed construction of k-dominating sets and applications
• Distributed Weighted Matching
• Algorithms – ESA 2004
• Constant-time distributed dominating set approximation

This page was built for publication: Distributed algorithms for weighted problems in sparse graphs