On the complexity of distributed stable matching with small messages

DOI10.1007/S00446-010-0105-5zbMATH Open1231.68153OpenAlexW1975264935MaRDI QIDQ660987FDOQ660987

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Distributed Computing: A Locality-Sensitive Approach
• College Admissions and the Stability of Marriage
• Complexity of network synchronization
• Distributed MST for constant diameter graphs
• 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
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (1)

• Local Matching Dynamics in Social Networks

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)