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.2019.18
URN: urn:nbn:de:0030-drops-113259
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11325/
Go to the corresponding LIPIcs Volume Portal

Ghaffari, Mohsen ; Portmann, Julian

Improved Network Decompositions Using Small Messages with Applications on MIS, Neighborhood Covers, and Beyond

pdf-format:
LIPIcs-DISC-2019-18.pdf (0.4 MB)

Abstract

Network decompositions, as introduced by Awerbuch, Luby, Goldberg, and Plotkin [FOCS'89], are one of the key algorithmic tools in distributed graph algorithms. We present an improved deterministic distributed algorithm for constructing network decompositions of power graphs using small messages, which improves upon the algorithm of Ghaffari and Kuhn [DISC'18]. In addition, we provide a randomized distributed network decomposition algorithm, based on our deterministic algorithm, with failure probability exponentially small in the input size that works with small messages as well. Compared to the previous algorithm of Elkin and Neiman [PODC'16], our algorithm achieves a better success probability at the expense of its round complexity, while giving a network decomposition of the same quality. As a consequence of the randomized algorithm for network decomposition, we get a faster randomized algorithm for computing a Maximal Independent Set, improving on a result of Ghaffari [SODA'19]. Other implications of our improved deterministic network decomposition algorithm are: a faster deterministic distributed algorithms for constructing spanners and approximations of distributed set cover, improving results of Ghaffari, and Kuhn [DISC'18] and Deurer, Kuhn, and Maus [PODC'19]; and faster a deterministic distributed algorithm for constructing neighborhood covers, resolving an open question of Elkin [SODA'04].

BibTeX - Entry

@InProceedings{ghaffari_et_al:LIPIcs:2019:11325,
  author =	{Mohsen Ghaffari and Julian Portmann},
  title =	{{Improved Network Decompositions Using Small Messages with Applications on MIS, Neighborhood Covers, and Beyond}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Jukka Suomela},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/11325},
  URN =		{urn:nbn:de:0030-drops-113259},
  doi =		{10.4230/LIPIcs.DISC.2019.18},
  annote =	{Keywords: Distributed Graph Algorithms, Network Decomposition, Maximal Independent Set, Neighborhood Cover}
}

Keywords: Distributed Graph Algorithms, Network Decomposition, Maximal Independent Set, Neighborhood Cover
Collection: 33rd International Symposium on Distributed Computing (DISC 2019)
Issue Date: 2019
Date of publication: 08.10.2019

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