1 Search Results for "Vojnovic, Milan"

Document
DOI: 10.4230/LIPIcs.STACS.2015.460
Communication Complexity of Approximate Matching in Distributed Graphs

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

Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)

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

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)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.STACS.2015.460,
  author =	{Huang, Zengfeng and Radunovic, Bozidar and Vojnovic, Milan and Zhang, Qin},
  title =	{{Communication Complexity of Approximate Matching in Distributed Graphs}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{460--473},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Mayr, Ernst W. and Ollinger, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.460},
  URN =		{urn:nbn:de:0030-drops-49348},
  doi =		{10.4230/LIPIcs.STACS.2015.460},
  annote =	{Keywords: approximate maximum matching, distributed computation, communication complexity}
}
  • Refine by Author
  • 1 Huang, Zengfeng
  • 1 Radunovic, Bozidar
  • 1 Vojnovic, Milan
  • 1 Zhang, Qin

  • Refine by Classification

  • Refine by Keyword
  • 1 approximate maximum matching
  • 1 communication complexity
  • 1 distributed computation

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2015

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-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact