The Match-Maker: Constant-Space Distributed Majority via Random Walks

DOI10.1007/978-3-319-21741-3_5zbMATH Open1428.68048OpenAlexW2259256267MaRDI QIDQ5207899FDOQ5207899

Authors: David D. Hamilton, Russell Martin, Leszek Gąsieniec, P. G. Spirakis 

Publication date: 14 January 2020

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

Full work available at URL: https://doi.org/10.1007/978-3-319-21741-3_5

Recommendations

• Distributed approximate maximum matching in the CONGEST model
• Distributed near-optimal matching
• Distributed near-optimal matching
• A note on weighted distributed match-making
• Distributed algorithm for approximating the maximum matching
• Dynamic and self-stabilizing distributed matching
• Distributed Algorithm for Better Approximation of the Maximum Matching
• Improved deterministic distributed matching via rounding
• Improved deterministic distributed matching via rounding

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Random walks on graphs (05C81) Distributed systems (68M14) Network protocols (68M12)

Cited In (4)

• Mathematical Foundations of Computer Science 2003
• Randomized Algorithms for Determining the Majority on Graphs
• Global majority consensus by local majority polling on graphs of a given degree sequence
• Determining majority in networks with local interactions and very small local memory

This page was built for publication: The Match-Maker: Constant-Space Distributed Majority via Random Walks

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