Search Results

Documents authored by Grösbacher, Martin


Document
An Improved Random Shift Algorithm for Spanners and Low Diameter Decompositions

Authors: Sebastian Forster, Martin Grösbacher, and Tijn de Vos

Published in: LIPIcs, Volume 217, 25th International Conference on Principles of Distributed Systems (OPODIS 2021)


Abstract
Spanners have been shown to be a powerful tool in graph algorithms. Many spanner constructions use a certain type of clustering at their core, where each cluster has small diameter and there are relatively few spanner edges between clusters. In this paper, we provide a clustering algorithm that, given k ≥ 2, can be used to compute a spanner of stretch 2k-1 and expected size O(n^{1+1/k}) in k rounds in the CONGEST model. This improves upon the state of the art (by Elkin, and Neiman [TALG'19]) by making the bounds on both running time and stretch independent of the random choices of the algorithm, whereas they only hold with high probability in previous results. Spanners are used in certain synchronizers, thus our improvement directly carries over to such synchronizers. Furthermore, for keeping the total number of inter-cluster edges small in low diameter decompositions, our clustering algorithm provides the following guarantees. Given β ∈ (0,1], we compute a low diameter decomposition with diameter bound O((log n)/β) such that each edge e ∈ E is an inter-cluster edge with probability at most β⋅ w(e) in O((log n)/β) rounds in the CONGEST model. Again, this improves upon the state of the art (by Miller, Peng, and Xu [SPAA'13]) by making the bounds on both running time and diameter independent of the random choices of the algorithm, whereas they only hold with high probability in previous results.

Cite as

Sebastian Forster, Martin Grösbacher, and Tijn de Vos. An Improved Random Shift Algorithm for Spanners and Low Diameter Decompositions. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 217, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{forster_et_al:LIPIcs.OPODIS.2021.16,
  author =	{Forster, Sebastian and Gr\"{o}sbacher, Martin and de Vos, Tijn},
  title =	{{An Improved Random Shift Algorithm for Spanners and Low Diameter Decompositions}},
  booktitle =	{25th International Conference on Principles of Distributed Systems (OPODIS 2021)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-219-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{217},
  editor =	{Bramas, Quentin and Gramoli, Vincent and Milani, Alessia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2021.16},
  URN =		{urn:nbn:de:0030-drops-157914},
  doi =		{10.4230/LIPIcs.OPODIS.2021.16},
  annote =	{Keywords: Spanner, low diameter decomposition, synchronizer, distributed graph algorithms}
}
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