English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We address the problem of testing whether a dynamic graph is temporallyconnected, i.e. a temporal path ({\em journey}) exists between all pairs ofvertices. We consider a discrete version of the problem, where the topology isgiven as an evolving graph $\G=\{G_1,G_2,...,G_{k}\}$ in which only the set of(directed) edges varies. Two cases are studied, depending on whether a singleedge or an unlimited number of edges can be crossed in a same $G_i$ (strictjourneys {\it vs} non-strict journeys). For strict journeys, two existingalgorithms designed for other problems can be adapted. However, we show that adedicated approach achieves a better time complexity than one of these twoalgorithms in all cases, and than the other one for those graphs whose densityis low at any time (though arbitrary over time). The time complexity of ouralgorithm is $O(k\mu n)$, where $k=|\G|$ is the number of time steps and$\mu=max(|E_i|)$ is the maximum {\em instant} density, to be contrasted with$m=|\cup E_i|$, the {\em cumulated} density. Indeed, it is not uncommon for amobility scenario to satisfy, for instance, both $\mu=o(n)$ and$m=\Theta(n^2)$. We characterize the key values of $k, \mu$ and $m$ for whichour algorithm should be used. For non-strict journeys, for which no algorithmis known, we show that a similar strategy can be used to answer the question,still in $O(k\mu n)$ time.

Un algorithme de test pour la connexit\'e temporelle des graphes dynamiques de faible densit\'e