Efficient Distributed Weighted Matchings on Trees

DOI10.1007/11780823_10MaRDI QIDQ3613648zbMATH OpenOpenAlexFDO

Authors Jaap-Henk Hoepman, Shay Kutten, Zvi Lotker

Publication date 12 March 2009

Published in Structural Information and Communication Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11780823_10

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15) Randomized algorithms (68W20)

Recommendations

• Distributed Weighted Matching
• Improved Distributed Approximate Matching
• Distributed algorithms for weighted problems in sparse graphs
• Distributed approximate matching
• Distributed approximate matching

Cited in

(10)

• Almost stable matchings by truncating the Gale-Shapley algorithm
• Fast primal-dual distributed algorithms for scheduling and matching problems
• Distributed Approximation Algorithms for Weighted Problems in Minor-Closed Families
• A note on weighted distributed match-making
• Distributed tree comparison with nodes of limited memory
• Distributed Weighted Matching
• Distributed maximum matching verification in CONGEST
• Distributed algorithms for weighted problems in sparse graphs
• A simple local 3-approximation algorithm for vertex cover
• Distributed approximation for maximum weight matching on bounded degree bounded integer weight graphs

This page was built for publication: Efficient Distributed Weighted Matchings on Trees

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