Distributed algorithms for weighted problems in sparse graphs

DOI10.1016/J.JDA.2005.07.006MaRDI QIDQ866546zbMATH OpenOpenAlexFDO

Authors Andrzej Czygrinow, Michal Hanckowiak

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 algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• Efficient Distributed Weighted Matchings on Trees
• Distributed Approximation Algorithms for Weighted Problems in Minor-Closed Families
• Distributed Weighted Matching
• Distributed Approximation Algorithms for Planar Graphs
• Fast Distributed Approximations in Planar Graphs

Cites work

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

Cited in

(9)

• Distributed Approximation Algorithms for Weighted Problems in Minor-Closed Families
• Distributed Weighted Matching
• The Complexity of Distributed Approximation of Packing and Covering Integer Linear Programs
• Efficient Distributed Weighted Matchings on Trees
• Distributed Approximation Algorithms for Planar Graphs
• Fast Distributed Approximations in Planar Graphs
• A new distributed approximation algorithm for the maximum weight independent set problem
• Distributed strategies for generating weight-balanced and doubly stochastic digraphs
• Distributed Weight Balancing Over Digraphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q866546)