Near-optimal distributed DFS in planar graphs. (English) Zbl 1515.68371
Richa, Andréa W. (ed.), 31st international symposium on distributed computing, DISC 2017, Vienna, Austria, October 16–20, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 91, Article 21, 16 p. (2017).
Summary: We present a randomized distributed algorithm that computes a Depth-First Search (DFS) tree in \(\widetilde{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 by B. Awerbuch [Inf. Process. Lett. 20, 147–150 (1985; Zbl 0573.68013)], which remains the best known for general graphs. Furthermore, this \(\widetilde{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.
For the entire collection see [Zbl 1423.68035].
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.
For the entire collection see [Zbl 1423.68035].
MSC:
68W15 | Distributed algorithms |
05C10 | Planar graphs; geometric and topological aspects of graph theory |
05C85 | Graph algorithms (graph-theoretic aspects) |
68R10 | Graph theory (including graph drawing) in computer science |
68W20 | Randomized algorithms |