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

DOI10.1007/978-3-319-21741-3_5MaRDI QIDQ5207899zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

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)