Communication complexity of approximate matching in distributed graphs

DOI10.4230/LIPICS.STACS.2015.460MaRDI QIDQ2955016zbMATH OpenOpenAlexFDO

Authors Zengfeng Huang, Bozidar Radunovic, Milan Vojnovic, Qin Zhang

Publication date 24 January 2017

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

zbMATH Keywords

approximate maximum matchingcommunication complexitydistributed computation

Mathematics Subject Classification ID

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

Recommendations

• Communication complexity of approximate maximum matching in the message-passing model
• Algorithms – ESA 2004
• Distributed approximate matching
• Maximum matchings in dynamic graph streams and the simultaneous communication model
• Distributed approximate matching

Cited in

(13)

• Communication complexity in vertex partition whiteboard model
• Communication complexity of approximate maximum matching in the message-passing model
• Economic efficiency requires interaction
• Message lower bounds via efficient network synchronization
• Lower bounds for number-in-hand multiparty communication complexity, made easy
• The Range of Topological Effects on Communication
• Maximum matchings in dynamic graph streams and the simultaneous communication model
• scientific article; zbMATH DE number 7559107 (Why is no real title available?)
• Robust communication-optimal distributed clustering algorithms
• Communication and Streaming Complexity of Approximate Pattern Matching
• Round compression for parallel matching algorithms
• The message complexity of distributed graph optimization
• Sketching approximability of all finite CSPs

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

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