**Algorithmic Aspects of Temporal Graphs***

Satellite workshop of ICALP 2018

Prague, Czech Republic

Monday 9 July 2018

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 G_{1}, G_{2}, ... 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 half-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.

Presentations are given by invitation only. Everyone is welcome to register and attend.

Arnaud Casteigts

Jessica Enright

Thomas Erlebach

Paola Flocchini

Dimitris Fotakis

Ralf Klasing

Matthieu Latapy

Clémence Magnien

Kitty Meeks

Rolf Niedermeier

Christos Zaroliagis

George B. Mertzios (Durham University, UK)

Paul G. Spirakis (University of Liverpool, UK)

Eleni C. Akrida (University of Liverpool, UK)

Viktor Zamaraev (Durham University, UK)

* Partially supported by the EPSRC grants EP/P020372/1 and EP/P02002X/1, and by the EEE/CS University of Liverpool Initiative NeST.