Distributed 2-Approximation Algorithm for the Semi-matching Problem

DOI10.1007/978-3-642-33651-5_15zbMATH Open1377.68314OpenAlexW175379075MaRDI QIDQ4909413FDOQ4909413

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

Publication date: 13 March 2013

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-33651-5_15

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Approximation algorithms (68W25) Distributed algorithms (68W15) Distributed systems (68M14)

Cited In (10)

• Solving the at-most-once problem with nearly optimal effectiveness
• Distributed backup placement in networks
• Improved bounds for distributed load balancing
• On the distributed complexity of the semi-matching problem
• A local approximation algorithm for minimum dominating set problem in anonymous planar networks
• Stochastic coordination in heterogeneous load balancing systems
• On computing an optimal semi-matching
• Brief announcement: Efficient load-balancing through distributed token dropping
• Distributed backup placement
• Brief Announcement: Distributed Approximations for the Semi-matching Problem

This page was built for publication: Distributed 2-Approximation Algorithm for the Semi-matching Problem

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