文章基本信息

标题：Near-Optimal Distributed DFS in Planar Graphs
本地全文：下载
作者：Mohsen Ghaffari ; Merav Parter
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：91
页码：21:1-21:16
DOI：10.4230/LIPIcs.DISC.2017.21
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：congest model; planar graphs; separator