Communication complexity of approximate matching in distributed graphs

DOI10.4230/LIPIcs.STACS.2015.460zbMath1355.68100OpenAlexW2294952190MaRDI QIDQ2955016

Bozidar Radunovic, Qin Zhang, Milan Vojnovic, Zengfeng Huang

Publication date: 24 January 2017

Full work available at URL: https://doi.org/10.4230/LIPIcs.STACS.2015.460

zbMATH Keywords

communication complexitydistributed computationapproximate maximum matching

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Distributed algorithms (68W15)

Related Items (8)

The Range of Topological Effects on Communication ⋮ When distributed computation is communication expensive ⋮ Round Compression for Parallel Matching Algorithms ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Economic efficiency requires interaction ⋮ Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy ⋮ Message lower bounds via efficient network synchronization

This page was built for publication: Communication complexity of approximate matching in distributed graphs