Complexity of dynamic graph exploration by a mobile agent
type: Dataset
description: In this thesis, we study the complexity of the problem of exploration by a mobile agent in dynamic graphs. A mobile entity (called agent) moving in a dynamic graph has to traverse/visit each of its vertices at least once. This fundamental problem in computating by mobile agents has been well-studied in static graphs since the original paper of Claude Shannon. However, for highly dynamic graphs, only the case of periodic dynamic graphs has been studied. We study this problem in two families of dynamic graphs, periodically-varying graphs (PV-graphs) and T-interval-connected dynamic graphs. The obtained results improve the existing results and give optimal bounds on the studied problems. A PV-graph is defined by a set of carriers infinitely following their prescribed route along the network stations. In 2013, Flocchini, Mans and Santoro studied the problem in the case when the agent must always travel on the carriers and thus cannot wait at a station. Our work investigates the ability of an agent that can wait at the stations. We exhibit necessary and sufficient conditions for the problem to be solvable in this context, and we prove that waiting at the stations allows the agent to reduce the worst-case optimal number of moves by a multiplicative factor of at least $\Theta(p)$, while the time complexity is reduced to $\Theta(n\cdot p)$, where $n$, $k$, and $p$ denote respectively the number of sites, the number of carriers, and the maximal period. (In any connected PV-graph, we have $n \leq k\cdot p$.) We also show some complementary optimal results in specific cases (same period for all carriers, highly connected PV-graphs). Finally this ability allows the agent to produce a complete map of the PV-graph, in addition to just explore it. In the second part of the thesis, we considered the same problem (exploration) in T-interval-connected dynamic graphs. A dynamic graph is T-interval-connected ($T \geq 1$) if for every consecutive $T$ rounds, there exists a stable connec…
issued: 2026-05-05T20:46:13.450321
language: fr
modified: 2026-05-05T20:46:13.450325
contact point: Organization
  fn: CCSD
keyword: agent-mobile
keyword: dynamic-graphs
keyword: exploration
keyword: graphe-dynamique
keyword: infoeu-reposemanticsdoctoralthesis
keyword: infoinfo-cccomputer-science-cscomputational-complexity-cscc
keyword: infoinfo-dscomputer-science-csdata-structures-and-algorithms-csds
keyword: infoinfo-rbcomputer-science-csrobotics-csro
keyword: mathmath-comathematics-mathcombinatorics-mathco
keyword: mobile-agent
keyword: pv-graphe
keyword: pv-graphs
keyword: t-interval-connected
keyword: t-intervalle-connexite
keyword: theses
landing page: https://theses.hal.science/tel-00965926

Complexity of dynamic graph exploration by a mobile agent
type: Distribution
format: HTML
issued: 2026-05-05T20:46:13.455003
modified: 2026-05-05T20:46:13.423636
access URL: https://theses.hal.science/tel-00965926

test_moissonnage_selune
type: Agent