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

distributed complexitystable marriagestable matching problem

Mathematics Subject Classification ID

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

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

• 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
• 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?)
• Improved Distributed Approximate Matching
• The price of being near-sighted

Cited in

(7)

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