On the distributed complexity of the semi-matching problem

DOI10.1016/j.jcss.2016.05.001zbMath1348.68293OpenAlexW2431409430MaRDI QIDQ736606

Wojciech Wawrzyniak, Michał Hanćkowiak, Andrzej Czygrinow, Edyta Szymańska

Publication date: 4 August 2016

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2016.05.001

zbMATH Keywords

distributed algorithmssemi-matching

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) Distributed algorithms (68W15)

Related Items (1)

Wake up and join me! An energy-efficient algorithm for maximal matching in radio networks

Cites Work

• Unnamed Item
• Unnamed Item
• Approximating min sum set cover
• Survey of local algorithms
• Brief Announcement: Distributed Approximations for the Semi-matching Problem
• On Computing an Optimal Semi-matching
• Distributed Approximate Matching
• Faster Algorithms for Semi-matching Problems (Extended Abstract)
• Distributed Computing: A Locality-Sensitive Approach
• Distributed 2-Approximation Algorithm for the Semi-matching Problem
• Semi-matchings for bipartite graphs and load balancing

This page was built for publication: On the distributed complexity of the semi-matching problem