1. Exploration of Dynamic Cactuses with Sub-logarithmic Overhead
- Author
-
David Ilcinkas, Ahmed Mouhamadou Wade, Laboratoire Bordelais de Recherche en Informatique (LaBRI), Université de Bordeaux (UB)-Centre National de la Recherche Scientifique (CNRS)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB), Laboratoire Traitement de l’Information et Systèmes Intelligents (LTISI), Ecole Polytechnique de Thiès, A. M. Wade is partially supported by the African Center of Excellence in Mathematics, Computer Scienceand ICT (CEA-MITIC)., ANR-16-CE40-0023,DESCARTES,Abstraction modulaire pour le calcul distribué(2016), and ANR-16-CE25-0009,ESTATE,Auto-stabilisation et amélioration de la sûreté dans les environnements distribués évoluant dans le temps(2016)
- Subjects
Mobile agent ,Ring (mathematics) ,Logarithm ,Cactus graph ,0102 computer and information sciences ,02 engineering and technology ,Binary logarithm ,01 natural sciences ,Upper and lower bounds ,Theoretical Computer Science ,Vertex (geometry) ,Combinatorics ,Connectivity over time ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Simple (abstract algebra) ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,Exploration ,[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC] ,Connectivity ,Dynamic graphs ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
We study the problem of exploration by a mobile entity (agent) of a class of dynamic networks, namely constantly connected dynamic graphs. This problem has already been studied in the case where the agent knows the dynamics of the graph and the underlying graph is a ring of n vertices (Ilcinkas and Wade 2018). In this paper, we consider the same problem and we suppose that the underlying graph is a cactus graph (a connected graph in which any two simple cycles have at most one vertex in common). We propose an algorithm that allows the agent to explore these dynamic graphs in at most $O(n\frac {\log n}{\log \log n})$ time units. We show that the lower bound of the algorithm is ${\varOmega }(n\frac {\log n}{(\log \log n)^{2}})$ time units (for infinitely many n).
- Published
- 2020
- Full Text
- View/download PDF