https://www.dagstuhl.de/21171

25. – 30. April 2021, Dagstuhl-Seminar 21171

Temporal Graphs: Structure, Algorithms, Applications

Organisatoren

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

Auskunft zu diesem Dagstuhl-Seminar erteilen

Simone Schilke zu administrativen Fragen

Shida Kunz zu wissenschaftlichen Fragen

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

Dokumentation

In der Reihe Dagstuhl Reports werden alle Dagstuhl-Seminare und Dagstuhl-Perspektiven-Workshops dokumentiert. Die Organisatoren stellen zusammen mit dem Collector des Seminars einen Bericht zusammen, der die Beiträge der Autoren zusammenfasst und um eine Zusammenfassung ergänzt.

 

Download Übersichtsflyer (PDF).

Publikationen

Es besteht weiterhin die Möglichkeit, eine umfassende Kollektion begutachteter Arbeiten in der Reihe Dagstuhl Follow-Ups zu publizieren.

Dagstuhl's Impact

Bitte informieren Sie uns, wenn eine Veröffentlichung ausgehend von
Ihrem Seminar entsteht. Derartige Veröffentlichungen werden von uns in der Rubrik Dagstuhl's Impact separat aufgelistet  und im Erdgeschoss der Bibliothek präsentiert.