Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Ghaffari, Mohsen; Parter, Merav License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-80195


Near-Optimal Distributed DFS in Planar Graphs



We present a randomized distributed algorithm that computes a Depth-First Search (DFS) tree in ~O(D) rounds, in any planar network G=(V,E) with diameter D, with high probability. This is the first sublinear-time distributed DFS algorithm, improving on a three decades-old O(n) algorithm of Awerbuch (1985), which remains the best known for general graphs. Furthermore, this ~O(D) round complexity is nearly-optimal as Omega(D) is a trivial lower bound. A key technical ingredient in our results is the development of a distributed method for (recursively) computing a separator path, which is a path whose removal from the graph leaves connected components that are all a constant factor smaller. We believe that the general method we develop for computing path separators recursively might be of broader interest, and may provide the first step towards solving many other problems.

BibTeX - Entry

  author =	{Mohsen Ghaffari and Merav Parter},
  title =	{{Near-Optimal Distributed DFS in Planar Graphs}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{21:1--21: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 =		{},
  URN =		{urn:nbn:de:0030-drops-80195},
  doi =		{10.4230/LIPIcs.DISC.2017.21},
  annote =	{Keywords: congest model, planar graphs, separator}

Keywords: congest model, planar graphs, separator
Seminar: 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