Document Open Access Logo

Communication Complexity of Approximate Matching in Distributed Graphs

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

PDF

File

Thumbnail PDF
PDF
LIPIcs.STACS.2015.460.pdf
  • Filesize: 0.7 MB
  • 14 pages

Document Identifiers

Subject Classification

Keywords
  • approximate maximum matching
  • distributed computation
  • communication complexity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

In this paper we consider the communication complexity of approximation algorithms for maximum matching in a graph in the message-passing model of distributed computation. The input graph consists of n vertices and edges partitioned over a set of k sites. The output is an \alpha-approximate maximum matching in the input graph which has to be reported by one of the sites. We show a lower bound on the communication complexity of \Omega(\alpha^2 k n) and show that it is tight up to poly-logarithmic factors. This lower bound also applies to other combinatorial problems on graphs in the message-passing computation model, including max-flow and graph sparsification.

Cite As Get BibTex

Zengfeng Huang, Bozidar Radunovic, Milan Vojnovic, and Qin Zhang. Communication Complexity of Approximate Matching in Distributed Graphs. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 460-473, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.STACS.2015.460

Author Details

Zengfeng Huang
Bozidar Radunovic
Milan Vojnovic
Qin Zhang
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact