License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2019.78
URN: urn:nbn:de:0030-drops-111991
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11199/
Go to the corresponding LIPIcs Volume Portal

Ravi, R. ; Rudenko, Oleksandr

Multicommodity Multicast, Wireless and Fast

pdf-format:
LIPIcs-ESA-2019-78.pdf (3 MB)

Abstract

We study rumor spreading in graphs, specifically multicommodity multicast problem under the wireless model: given source-destination pairs in the graph, one needs to find the fastest schedule to transfer information from each source to the corresponding destination. Under the wireless model, nodes can transmit to any subset of their neighbors in synchronous time steps, as long as they either transmit or receive from at most one transmitter during the same time step. We improve approximation ratio for this problem from O~(n^(2/3)) to O~(n^((1/2) + epsilon)) on n-node graphs. We also design an algorithm that satisfies p given demand pairs in O(OPT + p) steps, where OPT is the length of an optimal schedule, by reducing it to the well-studied packet routing problem. In the case where underlying graph is an n-node tree, we improve the previously best-known approximation ratio of O((log n)/(log log n)) to 3. One consequence of our proof is a simple constructive rule for optimal broadcasting in a tree under a widely studied telephone model.

BibTeX - Entry

@InProceedings{ravi_et_al:LIPIcs:2019:11199,
  author =	{R. Ravi and Oleksandr Rudenko},
  title =	{{Multicommodity Multicast, Wireless and Fast}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{78:1--78:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-124-5},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{144},
  editor =	{Michael A. Bender and Ola Svensson and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11199},
  URN =		{urn:nbn:de:0030-drops-111991},
  doi =		{10.4230/LIPIcs.ESA.2019.78},
  annote =	{Keywords: Rumor, scheduling, broadcast, multicommodity, multicast, optimization algorithms, approximation, packet routing}
}

Keywords: Rumor, scheduling, broadcast, multicommodity, multicast, optimization algorithms, approximation, packet routing
Collection: 27th Annual European Symposium on Algorithms (ESA 2019)
Issue Date: 2019
Date of publication: 06.09.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI