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

A graph whose edges only appear at certain points in time is called atemporal graph (among other names). These graphs are temporally connected ifall ordered pairs of vertices are connected by a path that traverses edges inchronological order (a temporal path). Reachability in temporal graphs departssignificantly from standard reachability; in particular, it is not transitive,with structural and algorithmic consequences. For instance, temporallyconnected graphs do not always admit spanning trees, i.e., subsets of edgesthat form a tree and preserve temporal connectivity among the nodes.  In this paper, we revisit fundamental questions about the loss ofuniversality of spanning trees. To start, we show that deciding if a spanningtree exists in a given temporal graph is NP-complete. What could be appropriatereplacement for the concept? Beyond having minimum size, spanning trees enjoythe feature of enabling reachability along the same underlying paths in bothdirections, a pretty uncommon feature in temporal graphs. We explorerelaxations in this direction and show that testing the existence ofbidirectional spanning structures (bi-spanners) is tractable in general. On thedown side, finding \emph{minimum} such structures is NP-hard even in simpletemporal graphs. Still, the fact that bidirectionality can be testedefficiently may find applications, e.g. for routing and security, and thecorresponding primitive that we introduce in the algorithm may be ofindependent interest.

In search of the lost tree: Hardness and relaxation of spanning trees in temporal graphs