1 Search Results for "Sardeshmukh, Vivek B."


Document
Super-Fast MST Algorithms in the Congested Clique Using o(m) Messages

Authors: Sriram V. Pemmaraju and Vivek B. Sardeshmukh

Published in: LIPIcs, Volume 65, 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)


Abstract
In a sequence of recent results (PODC 2015 and PODC 2016), the running time of the fastest algorithm for the minimum spanning tree (MST) problem in the Congested Clique model was first improved to O(log(log(log(n)))) from O(log(log(n))) (Hegeman et al., PODC 2015) and then to O(log^*(n)) (Ghaffari and Parter, PODC 2016). All of these algorithms use Theta(n^2) messages independent of the number of edges in the input graph. This paper positively answers a question raised in Hegeman et al., and presents the first "super-fast" MST algorithm with o(m) message complexity for input graphs with m edges. Specifically, we present an algorithm running in O(log^*(n)) rounds, with message complexity ~O(sqrt{m * n}) and then build on this algorithm to derive a family of algorithms, containing for any epsilon, 0 < epsilon <= 1, an algorithm running in O(log^*(n)/epsilon) rounds, using ~O(n^{1 + epsilon}/epsilon) messages. Setting epsilon = log(log(n))/log(n) leads to the first sub-logarithmic round Congested Clique MST algorithm that uses only ~O(n) messages. Our primary tools in achieving these results are (i) a component-wise bound on the number of candidates for MST edges, extending the sampling lemma of Karger, Klein, and Tarjan (Karger, Klein, and Tarjan, JACM 1995) and (ii) Theta(log(n))-wise-independent linear graph sketches (Cormode and Firmani, Dist. Par. Databases, 2014) for generating MST candidate edges.

Cite as

Sriram V. Pemmaraju and Vivek B. Sardeshmukh. Super-Fast MST Algorithms in the Congested Clique Using o(m) Messages. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 47:1-47:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)


Copy BibTex To Clipboard

@InProceedings{pemmaraju_et_al:LIPIcs.FSTTCS.2016.47,
  author =	{Pemmaraju, Sriram V. and Sardeshmukh, Vivek B.},
  title =	{{Super-Fast MST Algorithms in the Congested Clique Using o(m) Messages}},
  booktitle =	{36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016)},
  pages =	{47:1--47:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-027-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{65},
  editor =	{Lal, Akash and Akshay, S. and Saurabh, Saket and Sen, Sandeep},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2016.47},
  URN =		{urn:nbn:de:0030-drops-68827},
  doi =		{10.4230/LIPIcs.FSTTCS.2016.47},
  annote =	{Keywords: Congested Clique, Minimum Spanning Tree, Linear Graph Sketches, Message Complexity, Sampling}
}
  • Refine by Author
  • 1 Pemmaraju, Sriram V.
  • 1 Sardeshmukh, Vivek B.

  • Refine by Classification

  • Refine by Keyword
  • 1 Congested Clique
  • 1 Linear Graph Sketches
  • 1 Message Complexity
  • 1 Minimum Spanning Tree
  • 1 Sampling

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

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