Document Open Access Logo

Near-Optimal Distributed DFS in Planar Graphs

Authors Mohsen Ghaffari, Merav Parter

PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.21.pdf
  • Filesize: 0.96 MB
  • 16 pages

Document Identifiers

Author Details

Mohsen Ghaffari
Merav Parter

Cite As Get BibTex

Mohsen Ghaffari and Merav Parter. Near-Optimal Distributed DFS in Planar Graphs. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.DISC.2017.21

Abstract

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.

Subject Classification

Keywords
  • congest model
  • planar graphs
  • separator

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. A. Aggarwal and R. Anderson. A random nc algorithm for depth first search. In STOC, pages 325-334, 1987. Google Scholar
  2. Richard Anderson. A parallel algorithm for the maximal path problem. Combinatorica, 7(4):315-326, 1987. Google Scholar
  3. RJ Anderson. A parallel algorithm for depth-first search. 1986. In Extended abstract, 1986. Google Scholar
  4. Baruch Awerbuch. A new distributed depth-first-search algorithm. Information Processing Letters, 20(3):147-150, 1985. Google Scholar
  5. Keren Censor-Hillel, Mohsen Ghaffari, and Fabian Kuhn. Distributed connectivity decomposition. In PODC, 2014. Google Scholar
  6. Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, and Roger Wattenhofer. Distributed verification and hardness of distributed approximation. In STOC, pages 363-372, 2011. Google Scholar
  7. Atish Das Sarma, Danupon Nanongkai, and Gopal Pandurangan. Fast distributed random walks. In PODC, pages 161-170, 2009. Google Scholar
  8. Atish Das Sarma, Danupon Nanongkai, Gopal Pandurangan, and Prasad Tetali. Efficient distributed random walks with applications. In PODC, pages 201-210, 2010. Google Scholar
  9. Michael Elkin. Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem. In STOC, pages 331-340, 2004. Google Scholar
  10. Shimon Even. Graph algorithms. Cambridge University Press, 2011. Google Scholar
  11. Stephen Fenner, Rohit Gurjar, and Thomas Thierauf. Bipartite perfect matching is in quasi-nc. In STOC, pages 754-763. ACM, 2016. Google Scholar
  12. Silvio Frischknecht, Stephan Holzer, and Roger Wattenhofer. Networks cannot compute their diameter in sublinear time. In SODA, pages 1150-1162, 2012. Google Scholar
  13. J.A. Garay, S. Kutten, and D. Peleg. A sub-linear time distributed algorithm for minimum-weight spanning trees. In FOCS, 1993. Google Scholar
  14. M. Ghaffari and F. Kuhn. Distributed minimum cut approximation. In DISC, pages 1-15, 2013. Google Scholar
  15. Mohsen Ghaffari. Near-optimal distributed approximation of minimum-weight connected dominating set. In International Colloquium on Automata, Languages, and Programming, pages 483-494. Springer, 2014. Google Scholar
  16. Mohsen Ghaffari and Bernhard Haeupler. Distributed algorithms for planar networks i: Planar embedding. In PODC, pages 29-38, 2016. Google Scholar
  17. Mohsen Ghaffari and Bernhard Haeupler. Distributed algorithms for planar networks ii: Low-congestion shortcuts, mst, and min-cut. In SODA, pages 202-219, 2016. Google Scholar
  18. Mohsen Ghaffari, Andreas Karrenbauer, Fabian Kuhn, Christoph Lenzen, and Boaz Patt-Shamir. Near-optimal distributed maximum flow. In PODC, pages 81-90. ACM, 2015. Google Scholar
  19. Mohsen Ghaffari and Christoph Lenzen. Near-optimal distributed tree embedding. In International Symposium on Distributed Computing, pages 197-211. Springer, 2014. Google Scholar
  20. Andrew V Goldberg, Serge A Plotkin, and Pravin M Vaidya. Sublinear-time parallel algorithms for matching and related problems. In Foundations of Computer Science, 1988., 29th Annual Symposium on, pages 174-185. IEEE, 1988. Google Scholar
  21. Bernhard Haeupler, Taisuke Izumi, and Goran Zuzic. Low-congestion shortcuts without embedding. In PODC, pages 451-460. ACM, 2016. Google Scholar
  22. Bernhard Haeupler, Taisuke Izumi, and Goran Zuzic. Near-optimal low-congestion shortcuts on bounded parameter graphs. In International Symposium on Distributed Computing, pages 158-172. Springer, 2016. Google Scholar
  23. Torben Hagerup. Planar depth-first search in o($$1logn) parallel time. SIAM Journal on Computing, 19(4):678-704, 1990. Google Scholar
  24. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. A deterministic almost-tight distributed algorithm for approximating single-source shortest paths. In STOC, pages 489-498, 2016. Google Scholar
  25. Stephan Holzer and Roger Wattenhofer. Optimal distributed all pairs shortest paths and applications. In PODC, pages 355-364, 2012. Google Scholar
  26. Ming-Yang Kao. All graphs have cycle separators and planar directed depth-first search is in dnc. In Aegean Workshop on Computing, pages 53-63. Springer, 1988. Google Scholar
  27. Shay Kutten and David Peleg. Fast distributed construction of k-dominating sets and applications. In PODC, pages 238-251, 1995. Google Scholar
  28. Christoph Lenzen and Boaz Patt-Shamir. Fast routing table construction using small messages: Extended abstract. In STOC, pages 381-390, 2013. Google Scholar
  29. Christoph Lenzen and Boaz Patt-Shamir. Improved distributed steiner forest construction. In PODC, 2014. Google Scholar
  30. Richard J Lipton and Robert Endre Tarjan. A separator theorem for planar graphs. SIAM Journal on Applied Mathematics, 36(2):177-189, 1979. Google Scholar
  31. Kurt Mehlhorn and Peter Sanders. Graph traversal. Algorithms and Data Structures: The Basic Toolbox, pages 175-189, 2008. Google Scholar
  32. Danupon Nanongkai. Distributed approximation algorithms for weighted shortest paths. In STOC, 2014. Google Scholar
  33. Danupon Nanongkai, Atish Das Sarma, and Gopal Pandurangan. A tight unconditional lower bound on distributed randomwalk computation. In PODC, pages 257-266, 2011. Google Scholar
  34. Danupon Nanongkai and Hsin-Hao Su. Almost-tight distributed minimum cut algorithms. In International Symposium on Distributed Computing, pages 439-453. Springer, 2014. Google Scholar
  35. Jaroslav Nešetřil, Eva Milková, and Helena Nešetřilová. Otakar boruvka on minimum spanning tree problem translation of both the 1926 papers, comments, history. Discrete Mathematics, 233(1):3-36, 2001. Google Scholar
  36. David Peleg. Distributed Computing: A Locality-sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 2000. Google Scholar
  37. David Peleg and Vitaly Rubinovich. A near-tight lower bound on the time complexity of distributed MST construction. In FOCS, pages 253-, 1999. Google Scholar
  38. John H Reif. Depth-first search is inherently sequential. IPL, 20(5):229-234, 1985. Google Scholar
  39. Gregory E Shannon. A linear-processor algorithm for depth-first search in planar graphs. IPL, 29(3):119-123, 1988. Google Scholar
  40. Steven S Skiena. The algorithm design manual: Text, volume 1. Springer Science &Business Media, 1998. Google Scholar
  41. Justin R Smith. Parallel algorithms for depth-first searches i. planar graphs. SIAM Journal on Computing, 15(3):814-830, 1986. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact