On the complexity of distributed stable matching with small messages

DOI10.1007/S00446-010-0105-5MaRDI QIDQ660987zbMATH OpenOpenAlexFDO

Authors Alex Kipnis, Boaz Patt-Shamir

Publication date 6 February 2012

Published in Distributed Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00446-010-0105-5

zbMATH Keywords

stable marriagedistributed complexitystable matching problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Distributed systems (68M14)

Recommendations

• Distributed Weighted Stable Marriage Problem
• Fast distributed almost stable matchings
• Communication requirements for stable marriages
• Distributed stable matching with similar preference lists
• Distributed near-optimal matching

Cites work

• scientific article; zbMATH DE number 1617265 (Why is no real title available?)
• scientific article; zbMATH DE number 2086256 (Why is no real title available?)
• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• scientific article; zbMATH DE number 1369412 (Why is no real title available?)
• A near-tight lower bound on the time complexity of distributed minimum-weight spanning tree construction
• College Admissions and the Stability of Marriage
• Complexity of network synchronization
• Distributed Computing: A Locality-Sensitive Approach
• Distributed MST for constant diameter graphs
• Improved Distributed Approximate Matching
• The price of being near-sighted

Cited in

(6)

• Local matching dynamics in social networks
• Self-stabilizing distributed stable marriage
• Communication requirements for stable marriages
• Distributed near-optimal matching
• Distributed stable matching with similar preference lists
• Jealousy graphs: structure and complexity of decentralized stable matching

This page was built for publication: On the complexity of distributed stable matching with small messages

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