Tight bounds on exploration of constantly connected cacti-paths
LTISI laboratory GIT, Polytechnic School of Thiès (EPT), Thiès, Sénégal.
Research Article
World Journal of Advanced Research and Reviews, 2021, 12(01), 355–361
Article DOI: 10.30574/wjarr.2021.12.1.0534
Publication history:
Received on 15 September 2021; revised on 18 October 2021; accepted on 20 October 2021
Abstract:
In this paper, we study the necessary and sufficient time to explore constantly connected dynamics graphs by a mobile entity (agent). A dynamic graph is constantly connected if for each time units, there exists a stable connected spanning tree [10]. We focus on the case where the underlying graph is a cactus-path (graph reduced to a path of 
rings in which two neighbor rings have at most one vertex in common) and we assume that the agent knows the dynamics of the graph. We show that time units are necessary and sufficient to explore any constantly connected dynamic graph based on the cactus-path (composed of two same size rings). The upper bound is generalized on dynamic graphs based on cacti-paths with rings. We show that for any constantly connected dynamic graph of size based on a cactus-path, time units are sufficient to explore the graph, with the length of the path, the size of the dynamic graph and the size of the ring which is at position starting from left to right.
rings in which two neighbor rings have at most one vertex in common) and we assume that the agent knows the dynamics of the graph. We show that 
time units are necessary and sufficient to explore any constantly connected dynamic graph based on the cactus-path 
(composed of two same size rings
). The upper bound is generalized on dynamic graphs based on cacti-paths with rings. We show that for any constantly connected dynamic graph of size 
based on a cactus-path, 
time units are sufficient to explore the graph, with the length of the path, 
the size of the dynamic graph and 
the size of the ring which is at position 
starting from left to right.Keywords:
Dynamic graph; Exploration; Mobile agent; Cactus-path
Full text article in PDF:
Copyright information:
Copyright © 2021 Author(s) retain the copyright of this article. This article is published under the terms of the Creative Commons Attribution Liscense 4.0