On the distributed complexity of the semi-matching problem
DOI10.1016/J.JCSS.2016.05.001zbMATH Open1348.68293OpenAlexW2431409430MaRDI QIDQ736606FDOQ736606
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
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
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)
Cites Work
- Title not available (Why is that?)
- Distributed Computing: A Locality-Sensitive Approach
- Distributed 2-approximation algorithm for the semi-matching problem
- Semi-matchings for bipartite graphs and load balancing
- Approximating min sum set cover
- Faster algorithms for semi-matching problems (extended abstract)
- Survey of local algorithms
- Title not available (Why is that?)
- Distributed approximate matching
- Brief announcement: Distributed approximations for the semi-matching problem
- On computing an optimal semi-matching
Cited In (7)
- An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs
- Title not available (Why is that?)
- Distributed 2-approximation algorithm for the semi-matching problem
- Wake up and join me! An energy-efficient algorithm for maximal matching in radio networks
- Brief announcement: Distributed approximations for the semi-matching problem
- Theory and Applications of Models of Computation
- On the Power of the Semi-Separated Pair Decomposition
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)
