https://www.dagstuhl.de/21171

April 25 – 30 , 2021, Dagstuhl Seminar 21171

Temporal Graphs: Structure, Algorithms, Applications

Organizers

Arnaud Casteigts (University of Bordeaux, FR)
Kitty Meeks (University of Glasgow, GB)
George B. Mertzios (Durham University, GB)
Rolf Niedermeier (TU Berlin, DE)

For support, please contact

Dagstuhl Service Team

Documents

Dagstuhl Report, Volume 11, Issue 3 Dagstuhl Report
List of Participants
Shared Documents
Dagstuhl Seminar Schedule [pdf]

Motivation

Traditionally, graphs (composed of vertices and edges) are used to abstractly model diverse real-world systems, where vertices and edges represent elementary system units and some kind of interactions between them, respectively. However, in modern systems, this modeling paradigm using static graphs may be too restrictive or oversimplifying, as interactions often change over time in a highly dynamic manner. For example, friendships are added and removed over time in a social network and links in a communication network may change dynamically, either according to a specific known pattern (satellites following a trajectory) or in an unpredictable manner (mobile ad-hoc networks). The common characteristic in all these application areas is that the system structure, i.e., graph topology, is subject to discrete changes over time. In particular, we are interested in scenarios where we have full information over the changes which happened in the past or will happen in the future. In such dynamically changing graphs the notion of vertex adjacency needs to be revisited and various graph concepts, e.g., reachability and connectedness, now crucially depend on the exact temporal ordering of the edges’ presence.

Correspondingly, a temporal graph is a graph whose edge set changes over time. Given a static underlying graph G, a temporal graph is obtained by assigning to every edge of G a set of nonnegative integer time-labels, indicating the discrete time steps in which this edge is active. Many notions and algorithms on static (i.e., non-temporal) graphs can be naturally transferred in a meaningful way to their temporal counterpart, while in other cases new approaches are needed to define the appropriate temporal notions. We note that, in most cases, the existence of the time dimension adds some degree of freedom in defining a specific temporal variant of a static problem. For example, depending on the application domain, the temporal analogue of a “shortest path” between two vertices can be translated as (a) the topologically shortest path, having the smallest number of edges, (b) the fastest path, having the smallest time duration, or (c) the foremost path, arriving as early as possible (regardless of the starting time). The variety of temporal analogues of static graph optimization problems naturally leads to fundamental algorithmic questions which are still far from being well understood. Notably, such topics are temporal in essence, which means that they cannot be defined in terms of the structure of the graph at a given instant.

In this one-week Dagstuhl Seminar, recent advances in the area of temporal graphs will be presented, discussed, and some of the current key challenges will be highlighted to better understand the many facets of the computational complexity of temporal graph problems. This research area grows and broadens internationally, and our aim is to bring together people from the various theoretical and practical subcommunities of temporal graphs in order to establish new and to strengthen existing links between these communities.

We plan to structure the seminar into four key areas (partially overlapping). (1) Models, Concepts, Classes, (2) Concrete Algorithmic Problems, (3) Distributed Aspects, and (4) Applications.

Motivation text license
  Creative Commons BY 3.0 DE
  Arnaud Casteigts, Kitty Meeks, George B. Mertzios, and Rolf Niedermeier

Classification

  • Data Structures And Algorithms
  • Discrete Mathematics
  • Social And Information Networks

Keywords

  • Models and Classes
  • Complex Network Analysis
  • Parameterized Complexity Analysis
  • Algorithm Engineering
  • Distributed Computing

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.