Résumé :

Separator sets have been utilized in algorithmic solutions for various classic problems in graph theory, including maximum matching, depth-first search (DFS), and Boolean circuits. However, their study in distributed models has been limited. In this talk, I will introduce distributed models and present the first deterministic algorithm in the CONGEST model that computes separator sets for planar graphs. Additionally, I will show how these sets can be employed to construct a DFS spanning tree in O(diam(G)) rounds, where diam(G) denotes the diameter of the graph, improving the best-known deterministic and distributed algorithm.