Papers on Flows over time

Comparison of Flows Over Time (Dynamic Flow) to Flow in Temporal Graphs

"Flows over time": you have a (static) graph where flow (e.g., goods, information, or people) moves through the edges, and each edge takes a certain amount of time to traverse. Time is considered as a resource or dimension that affects how flow is distributed over the graph.

• Key Characteristics:
  • The amount of flow depends not just on the capacities of the edges but also on how long it takes for the flow to traverse them.
  • You aim to optimize the flow over a period, maximizing the total flow reaching a destination by a certain time or minimizing the time required to send a specific amount of flow.
  • These problems usually involve constraints on capacities, edge traversal times, and sometimes even time-dependent capacities.
  • Examples include scheduling evacuation routes in disaster management or coordinating traffic flows over a day.
• Main Difference: Time is continuous or discrete, but the flow moves through the network over time, affecting when and how much flow reaches its destination.

Flow in temporal graphs: In temporal graphs, the graph structure itself changes over time. The availability of edges or vertices can depend on the time, the graph is not static. At each time step, a different "snapshot" of the graph is available, which allows certain flows but restricts others.

In Summary:

• Flows over time: The graph is static, but flow moves through it over time, and time directly affects when flow reaches its destination.
• Flow in temporal graphs: The graphs structure changes over time, affecting when and how flow can move.