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 consider the problem of assigning appearing times to the edges of adigraph in order to maximize the (average) temporal reachability between pairsof nodes. Motivated by the application to public transit networks, where edgescannot be scheduled independently one of another, we consider the setting wherethe edges are grouped into certain walks (called trips) in the digraph andwhere assigning the appearing time to the first edge of a trip forces theappearing times of the subsequent edges. In this setting, we show that, quitesurprisingly, it is NP-complete to decide whether there exists an assignment oftimes connecting a given pair of nodes. This result allows us to prove that theproblem of maximising the temporal reachability cannot be approximated within afactor better than some polynomial term in the size of the graph. We thus focuson the case where, for each pair of nodes, there exists an assignment of timessuch that one node is reachable from the other. We call this property strongtemporalisability. It is a very natural assumption for the application topublic transit networks. On the negative side, the problem of maximising thetemporal reachability remains hard to approximate within a factor $\sqrt$ n/12in that setting. Moreover, we show the existence of collections of trips thatare strongly temporalisable but for which any assignment of starting times tothe trips connects at most an O(1/ $\sqrt$ n) fraction of all pairs of nodes.On the positive side, we show that there must exist an assignment of times thatconnects a constant fraction of all pairs in the strongly temporalisable andsymmetric case, that is, when the set of trips to be scheduled is such that,for each trip, there is a symmetric trip visiting the same nodes in reverseorder. Keywords:edge labeling edge scheduled network network optimisationtemporal graph temporal path temporal reachability time assignment

On The Complexity of Maximizing Temporal Reachability via Trip Temporalisation