Building Fastest Broadcast Trees in Periodically-Varying Graphs
Delay-Tolerant Networks (DTNs) are characterized by a possible absence of end-to-end communication routes at any instant. Still, connectivity can generally be established over time and space. The optimality of a temporal path (journey) in this context can be defined in several terms, including topological (e.g. shortest in hops) and temporal (e.g. fastest, foremost). The combinatorial problem of computing shortest, foremost, and fastest journeys given full knowledge of the network schedule was addressed a decade ago. A recent line of research has focused on the distributed version of this problem, where foremost, shortest or fastest broadcast are performed without knowing the schedule beforehand.