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.DISC.2017.24
URN: urn:nbn:de:0030-drops-80085
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/8008/
Go to the corresponding LIPIcs Volume Portal

Grossman, Ofer ; Parter, Merav

Improved Deterministic Distributed Construction of Spanners

pdf-format:
LIPIcs-DISC-2017-24.pdf (0.6 MB)

Abstract

Graph spanners are fundamental graph structures with a wide range of applications in distributed networks. We consider a standard synchronous message passing model where in each round O(log n) bits can be transmitted over every edge (the CONGEST model).

The state of the art of deterministic distributed spanner constructions suffers from large messages. The only exception is the work of Derbel et al., which computes an optimal-sized (2k-1)-spanner but uses O(n^(1-1/k)) rounds.

In this paper, we significantly improve this bound. We present a deterministic distributed algorithm that given an unweighted n-vertex graph G = (V,E) and a parameter k > 2, constructs a (2k-1)-spanner with O(k n^(1+1/k)) edges within O(2^k n^(1/2 - 1/k)) rounds for every even k. For odd k, the number of rounds is O(2^k n^(1/2 - 1/(2k))). For the weighted case, we provide the first deterministic construction of a 3-spanner with O(n^(3/2)) edges that uses O(log n)-size messages and ~O(1) rounds. If the vertices have IDs in [1,Theta(n)], the spanner is computed in only 2 rounds!

BibTeX - Entry

@InProceedings{grossman_et_al:LIPIcs:2017:8008,
  author =	{Ofer Grossman and Merav Parter},
  title =	{{Improved Deterministic Distributed Construction of Spanners}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{24:1--24:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Andr{\'e}a W. Richa},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8008},
  URN =		{urn:nbn:de:0030-drops-80085},
  doi =		{10.4230/LIPIcs.DISC.2017.24},
  annote =	{Keywords: spanners, clustering, deterministic algorithms, congest model}
}

Keywords: spanners, clustering, deterministic algorithms, congest model
Collection: 31st International Symposium on Distributed Computing (DISC 2017)
Issue Date: 2017
Date of publication: 12.10.2017

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