On the complexity of distributed stable matching with small messages

DOI10.1007/s00446-010-0105-5zbMath1231.68153OpenAlexW1975264935MaRDI QIDQ660987

Boaz Patt-Shamir, Alex Kipnis

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) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Distributed systems (68M14)

Related Items (1)

Local Matching Dynamics in Social Networks

Cites Work

• A Near-Tight Lower Bound on the Time Complexity of Distributed Minimum-Weight Spanning Tree Construction
• Improved Distributed Approximate Matching
• The price of being near-sighted
• Complexity of network synchronization
• Distributed Computing: A Locality-Sensitive Approach
• College Admissions and the Stability of Marriage
• Distributed MST for constant diameter graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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