Anzeige
Erschienen in:
2014 | OriginalPaper | Buchkapitel
Exploration of Constantly Connected Dynamic Graphs Based on Cactuses
verfasst von : David Ilcinkas, Ralf Klasing, Ahmed Mouhamadou Wade
Erschienen in: Structural Information and Communication Complexity
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 [5]. 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
$2^{O(\sqrt{\log n})} n$
time units. We show that the lower bound of the algorithm is
$2^{\Omega(\sqrt{\log n})} n$
time units.