Near-optimal distributed DFS in planar graphs

DOI10.4230/LIPICS.DISC.2017.21zbMath1515.68371MaRDI QIDQ6487493

Mohsen Ghaffari, Merav Parter

Publication date: 3 February 2023

zbMATH Keywords

planar graphsseparatorcongest model

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Distributed algorithms (68W15)

Related Items (6)

Property testing of planarity in the \textsf{CONGEST} model ⋮ The energy complexity of diameter and minimum cut computation in bounded-genus networks ⋮ Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications ⋮ Brief Announcement: Distributed Construction of Near-Optimal Compact Routing Schemes for Planar Graphs ⋮ Compact distributed certification of planar graphs ⋮ Local certification of graphs with bounded genus

This page was built for publication: Near-optimal distributed DFS in planar graphs