On the distributed complexity of the semi-matching problem

DOI10.1016/J.JCSS.2016.05.001MaRDI QIDQ736606zbMATH OpenOpenAlexFDO

Authors Andrzej Czygrinow, Michal Hanckowiak, Edyta Szymańska, Wojciech Wawrzyniak

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)

Recommendations

• Distributed 2-approximation algorithm for the semi-matching problem
• On the distributed complexity of computing maximal matchings
• scientific article; zbMATH DE number 1303560
• Brief announcement: Distributed approximations for the semi-matching problem
• Distributed algorithms for matching in hypergraphs
• Distributed Algorithm for Better Approximation of the Maximum Matching
• Distributed algorithm for approximating the maximum matching
• Distributed approximation of maximum independent set and maximum matching
• On the Complexity of Distributed Splitting Problems
• Distributed local approximation algorithms for maximum matching in graphs and hypergraphs

Cites work

• scientific article; zbMATH DE number 3557814 (Why is no real title available?)
• scientific article; zbMATH DE number 1303560 (Why is no real title available?)
• Approximating min sum set cover
• Brief announcement: Distributed approximations for the semi-matching problem
• Distributed 2-approximation algorithm for the semi-matching problem
• Distributed Computing: A Locality-Sensitive Approach
• Distributed approximate matching
• Faster algorithms for semi-matching problems (extended abstract)
• On computing an optimal semi-matching
• Semi-matchings for bipartite graphs and load balancing
• Survey of local algorithms

Cited in

(9)

• Brief announcement: Distributed approximations for the semi-matching problem
• On the Power of the Semi-Separated Pair Decomposition
• Wake up and join me! An energy-efficient algorithm for maximal matching in radio networks
• scientific article; zbMATH DE number 1303560 (Why is no real title available?)
• Theory and Applications of Models of Computation
• Distributed 2-approximation algorithm for the semi-matching problem
• Improved bounds for distributed load balancing
• An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs
• Brief announcement: Efficient load-balancing through distributed token dropping

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

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