Anzeige
Erschienen in:
2013 | OriginalPaper | Buchkapitel
Exploration of the T-Interval-Connected Dynamic Graphs: The Case of the Ring
verfasst von : David Ilcinkas, 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
In this paper, we study the
T
-interval-connected dynamic graphs from the point of view of the time necessary and sufficient for their exploration by a mobile entity (agent). A dynamic graph (more precisely, an evolving graph) is
T
-interval-connected (
T
≥ 1) if, for every window of
T
consecutive time steps, there exists a connected spanning subgraph that is stable (always present) during this period. This property of connection stability over time was introduced by Kuhn, Lynch and Oshman [6] (STOC 2010). We focus on the case when the underlying graph is a ring of size
n
, and we show that the worst-case time complexity for the exploration problem is 2
n
−
T
− Θ(1) time units if the agent knows the dynamics of the graph, and
$n+ \frac{n}{\max\{1, T-1\} } (\delta-1) \pm \Theta(\delta)$
time units otherwise, where
δ
is the maximum time between two successive appearances of an edge.