Distributed Weighted Matching

DOI10.1007/978-3-540-30186-8_24MaRDI QIDQ5464202zbMATH OpenOpenAlexFDO

Authors Mirjam Wattenhofer, Roger Wattenhofer

Publication date 17 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-30186-8_24

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distributed algorithms (68W15)

Recommendations

• Efficient Distributed Weighted Matchings on Trees
• Improved Distributed Approximate Matching
• Distributed approximate matching
• Distributed approximate matching
• Distributed algorithms for weighted problems in sparse graphs

Cited in

(30)

• On the microscopic view of time and messages
• Distributed algorithms for weighted problems in sparse graphs
• An efficient distributed algorithm for maximum matching in general graphs
• Communication complexity of approximate maximum matching in the message-passing model
• Overlays with preferences: distributed, adaptive approximation algorithms for matching with preference lists
• Construction of optimal communication structures for weighted distributed match-making
• Distributed approximation for maximum weight matching on bounded degree bounded integer weight graphs
• A simple local 3-approximation algorithm for vertex cover
• A new analysis of a self-stabilizing maximum weight matching algorithm with approximation ratio 2
• Matching numbers in fuzzy graphs
• scientific article; zbMATH DE number 6866348 (Why is no real title available?)
• Distributed Approximation Algorithms for Weighted Problems in Minor-Closed Families
• Narrowing the \textsf{LOCAL-CONGEST} gaps in sparse networks via expander decompositions
• Proof labeling schemes
• scientific article; zbMATH DE number 4062556 (Why is no real title available?)
• Almost stable matchings by truncating the Gale-Shapley algorithm
• (1- ϵ )-Approximate Maximum Weighted Matching in poly(1/ ϵ , log n ) Time in the Distributed and Parallel Settings
• Constant-time local computation algorithms
• Distributed graph algorithms and their complexity: an introduction
• Fast primal-dual distributed algorithms for scheduling and matching problems
• Efficient distributed approximation algorithms via probabilistic tree embeddings
• Efficient Distributed Weighted Matchings on Trees
• Distributed approximate matching
• Multi-agent reinforcement learning for decentralized stable matching
• Distributed algorithms for covering, packing and maximum weighted matching
• Distributed maximum matching verification in CONGEST
• Distributed approximate maximum matching in the CONGEST model
• A note on weighted distributed match-making
• Improved deterministic distributed matching via rounding
• Distributed approximate matching

This page was built for publication: Distributed Weighted Matching

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