Algorithmic Aspects of Temporal Graphs V*

Satellite workshop of ICALP 2022
Paris, France
Monday 4 July 2022
(hybrid event)


    This workshop is devoted to the memory of Prof. Dr. Rolf Niedermeier,
    who has been a great scientist, a dear colleague and a good friend.


Topic

In modern systems the classical modeling paradigm using static graphs may be restrictive or oversimplifying, as the interactions among the elementary system units usually 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 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.

A temporal graph is a graph that changes over time. Assuming discrete time and a fixed set V of vertices, a temporal graph can be viewed as a discrete sequence G1, G2, ... of static graphs, each with vertex set V. Many notions and algorithms from the static case 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. In particular, some problems become radically different and substantially more difficult when the time dimension is additionally taken into account.

In this one-day workshop, recent advances in the area of temporal / dynamically changing graphs will be presented, as well as some of the key challenges will be highlighted. As this research area grows and broadens, our aim is to bring together people from theoretical and practical communities of temporal graphs in order to establish new and strengthen existing links between these communities.

This workshop is the sequel of the three previous workshops at ICALP 2018 (in Prague), ICALP 2019 (in Patras), ICALP 2020 (online), and ICALP 2021 (online).

The workshop is planed to run in hybrid mode, i.e. both online on zoom and in-person in Paris. Presentations are given by invitation only. Everyone is welcome to register and attend.


Practical information

Every presentation is given 30 minutes in total, which is expected to be 20-25 minutes of talk and 5-10 minutes for questions and change-over. The presentations are grouped into four sessions (two in the morning and two in the afternoon). Details of the invited speakers and the schedule can be found below.

The meeting will also be hosted on zoom at the following link:
https://durhamuniversity.zoom.us/j/96357567173?pwd=Mjlta1VBY2c4VERudFNURGJYSllUUT09
(Meeting ID: 963 5756 7173, Passcode: 964974)

For the online participants, we will have the following rules in place for the workshop to run smoothly:
- Please log in to the Zoom meeting using your REAL NAME and AFFILIATION, e.g. "Eleni Akrida, Durham University" or "Eleni Akrida, Durham".
- Please keep your microphone muted unless you would like to speak publicly, e.g. when you ask a question.
- Should you have any questions while a speaker is presenting, please try to not interrupt (unless you think it is necessary). Instead, please prefer write "Q" (for "Question") or "C" (for "Comment") in the chat. After the talk is over and it is time for questions, the chair of the session will advise those who have commented to ask their questions.


Video Recording


Information for onsite participants:

Location:

The workshop will be held in the Saint Père site of the Université Paris Cité (not the same place as the main ICALP conference) at: 45, rue des Saints-Pères, 75006 Paris. Please look for the room 'Avogadro F' on the 2nd floor of the building.

Environmental awareness:

This year, ICALP is promoting environmental awareness, so we ask those of you who will not participate at the main ICALP conference to please return your badges to the designated box after the end of the workshops' day.

Coffee breaks and lunch:

Coffee breaks will be served in the entrance hall. To get to where lunch is served, there will be a short (10') walk to the Tuieleries gardens. There will be volunteers who will guide groups of interested people there. Of course, any participant who doesn't wish to follow can stay in the building. Please be reminded that the rooms do not lock, so please do not leave any valuables in the rooms.


Workshop Schedule: All times below are in Central European Time (CET)

Abstracts