There is a whole area of research before the introduction of temporal graphs, studying the spreading of information in a communication network. Meaning, a time-dependent interaction between agents in order to transfer goods to other agents. Refer to the following survey

The two main problems studied in that area are gossiping and broadcasting.

Gossiping (all-to-all)

Gossiping

Traditional problem formulation, taken from [HHL88] section 2, pg 3:

Each member of a set $A$ of $n$ individuals knows a unique piece of information and must transmit it to every other person. The problem is solved by producing a sequence of unordered pairs $(i,j)$, $ij\in A$, each of which represents a phone call made between a pair of individuals. The sequence is such that during each call the two people involved exchange all of the information they know at that time; and such that at the end of the sequence of calls, everybody knows everything. Such a calling sequence, which completes gossiping among the $n$ people, is called complete.

Usual question: the minimum number of calls in a complete calling sequence among $n$ people

Variants of the basic Gossip Problem:

1. restricting the freedom in placing calls, i.e., a given person can only call a subset of the other people
2. restricting the calling process to one-way communication — directed
3. allowing $k$-party or conference calls
4. limiting the amount of redundant information which is sent
5. considering the amount of time, instead of the number of calls, necessary to complete gossiping”

Translated into a temporal graph problem:

Find a labeling for an undirected static graph, such that the resulting temporal graph is temporally connected.

What is the minimum number of labels/time needed to temporally connect a (un)directed graph?

Broadcasting (one-to-all)

Broadcasting

A major variant of the Gossip Problem, introduced by Slater in 1977. Traditional formulation, taken from [HHL88] section 3, pg 12:

Determining the minimum amount of time required for one person to transmit one piece of information to everyone else in a communication graph. This seemingly simple variation touched off a substantial amount of research into the theory and technology of broadcasting in communication, information and computer networks. In the remaining sections of this paper, we review this work. Broadcasting refers to the process of message dissemination in a communication network whereby a message, originated by one member, is transmitted to all members of the network.

Broadcasting is accomplished by placing a series of calls over the communication lines of the network. This is to be completed as quickly as possible subject to the constraints that:

1. each call involves only two vertices
2. each call requires one unit of time
3. a vertex can participate in only one call per unit of time
4. a vertex can only call a vertex to which it is adjacent

Restriction (5) above leads to the term “local” broadcasting.

Given a connected graph $G$ and a message originator, vertex $u$, it is natural to ask, “what is the minimum number of time units required to complete broadcasting from vertex $u$?”

We define the broadcast time of verfex $u$, $b(u)$, to equal this minimum time. It is easy to see that for any vertex $u$ in a connected graph $G$ with $n$ vertices, $b(u)\geq\lceil log_2n\rceil$, since during each time unit the number of informed vertices can at most double.

Translated into a temporal graph problem:

Flooding time

Reach All

Graph temporalisation (TC)