Brief announcement: Distributed approximations for the semi-matching problem

DOI10.1007/978-3-642-24100-0_18MaRDI QIDQ3095327zbMATH OpenOpenAlexFDO

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

Publication date 28 October 2011

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

Full work available at URL https://doi.org/10.1007/978-3-642-24100-0_18

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Deterministic scheduling theory in operations research (90B35) 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 the semi-matching problem
• An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs
• Theory and Applications of Models of Computation
• Semi-matchings for bipartite graphs and load balancing

Cites work

• scientific article; zbMATH DE number 1303560 (Why is no real title available?)
• Distributed 2-approximation algorithm for the semi-matching problem
• Faster algorithms for semi-matching problems (extended abstract)
• Semi-matchings for bipartite graphs and load balancing

Cited in

(7)

• On the distributed complexity of the semi-matching problem
• A local approximation algorithm for minimum dominating set problem in anonymous planar networks
• Distributed 2-approximation algorithm for the semi-matching problem
• Tight Approximation Bounds for the Seminar Assignment Problem
• Weak models of distributed computing, with connections to modal logic
• 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: Brief announcement: Distributed approximations for the semi-matching problem

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