DROPS

Document

DOI: 10.4230/LIPIcs.MFCS.2018.80

Tight Bounds for Deterministic h-Shot Broadcast in Ad-Hoc Directed Radio Networks

Authors: Aris Pagourtzis and Tomasz Radzik

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract

We consider the classical broadcast problem in ad-hoc (that is, unknown topology) directed radio networks with no collision detection, under the additional assumption that at most h transmissions (shots) are available per node. We focus on adaptive deterministic protocols for small values of h. We provide asymptotically matching lower and upper bounds for the cases h=2 and h=3. While for h=2 our bound is quadratic, similar to the bound obtained for oblivious protocols, for h=3 we prove a sub-quadratic bound of Theta(n^2 log log n / log n), where n is the number of nodes in the network. The latter is the first result showing an adaptive algorithm which is asymptotically faster than oblivious h-shot broadcast protocols, for which a tight quadratic bound is known for every constant h. Our upper bound for h=3 is constructive, making use of constructions of graphs with large girth. We also show an improved upper bound of O(n^(1+alpha/sqrt{h})) for h >= 4, where alpha is an absolute constant independent of h. Our upper bound for h >= 4 is non-constructive.

Cite as

Aris Pagourtzis and Tomasz Radzik. Tight Bounds for Deterministic h-Shot Broadcast in Ad-Hoc Directed Radio Networks. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 80:1-80:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{pagourtzis_et_al:LIPIcs.MFCS.2018.80,
  author =	{Pagourtzis, Aris and Radzik, Tomasz},
  title =	{{Tight Bounds for Deterministic h-Shot Broadcast in Ad-Hoc Directed Radio Networks}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{80:1--80:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.80},
  URN =		{urn:nbn:de:0030-drops-96629},
  doi =		{10.4230/LIPIcs.MFCS.2018.80},
  annote =	{Keywords: Ad-hoc radio networks, wireless networks, deterministic broadcast, adaptive protocols, limited transmissions}
}

Document

DOI: 10.4230/OASIcs.ATMOS.2006.684

Periodic Metro Scheduling

Authors: Evangelos Bampas, Georgia Kaouri, Michael Lampis, and Aris Pagourtzis

Published in: OASIcs, Volume 5, 6th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'06) (2006)

Abstract

We introduce the { extsc{Periodic Metro Sched-ul-ing}} ({ extsc{PMS}}) problem, which aims in generating a periodic timetable for a given set of routes and a given time period, in such a way that the minimum time distance between any two successive trains that pass from the same point of the network is maximized. This can be particularly useful in cases where trains use the same rail segment quite often, as happens in metropolitan rail networks. We present exact algorithms for ({ extsc{PMS}}) in chain and spider networks, and constant ratio approximation algorithms for ring networks and for a special class of tree networks. Some of our algorithms are based on a reduction to the { extsc{Path Coloring}} problem, while others rely on techniques specially designed for the new problem.

Cite as

Evangelos Bampas, Georgia Kaouri, Michael Lampis, and Aris Pagourtzis. Periodic Metro Scheduling. In 6th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'06). Open Access Series in Informatics (OASIcs), Volume 5, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{bampas_et_al:OASIcs.ATMOS.2006.684,
  author =	{Bampas, Evangelos and Kaouri, Georgia and Lampis, Michael and Pagourtzis, Aris},
  title =	{{Periodic Metro Scheduling}},
  booktitle =	{6th Workshop on Algorithmic Methods and Models for Optimization of Railways (ATMOS'06)},
  pages =	{1--15},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-01-9},
  ISSN =	{2190-6807},
  year =	{2006},
  volume =	{5},
  editor =	{Jacob, Riko and M\"{u}ller-Hannemann, Matthias},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2006.684},
  URN =		{urn:nbn:de:0030-drops-6841},
  doi =		{10.4230/OASIcs.ATMOS.2006.684},
  annote =	{Keywords: Train scheduling, path coloring, delay-tolerant scheduling, periodic timetabling}
}

Search Results

Documents authored by Pagourtzis, Aris

Tight Bounds for Deterministic h-Shot Broadcast in Ad-Hoc Directed Radio Networks

Abstract

Cite as

Periodic Metro Scheduling

Abstract

Cite as

Thanks for your feedback!

Could not send message