Algorithmic Aspects of Temporal Graphs
Lead Research Organisation:
University of Liverpool
Department Name: Computer Science
Abstract
Abstracts are not currently available in GtR for all funded research. This is normally because the abstract was not required at the time of proposal submission, but may be because it included sensitive information such as personal details.
Organisations
People |
ORCID iD |
| Paul Spirakis (Principal Investigator) |
Publications
Mertzios G
(2025)
The complexity of growing a graph
in Journal of Computer and System Sciences
Mertzios G
(2025)
The Complexity of Transitively Orienting Temporal Graphs
in Journal of Computer and System Sciences
Klobas N
(2024)
The complexity of computing optimum labelings for temporal connectivity
in Journal of Computer and System Sciences
| Description | We continued the work on natural temporal analogues of some non-path problems. We also introduced and analyzed the notion of transitive temporal networks, which extends the traditional notion of transitively orienting static graphs. This problem is an example of a new, and fundamentally different, type of temporal problems, which also gives rise to new temporal graph classes. We thoroughly examined stochastic temporal graphs where the links have some memory of their past existence affecting their probability to exist in the future. We have also worked on actively dynamic graphs (where the nodes can influence the existence of graph links in their neighborhood) and we examined what graph classes can be distributedly constructed in short time in such actively dynamic networks. |
| Exploitation Route | Our publications are available to all (open) and we also organize a yearly workshop for 4 consecutive years during the ICALP Conference (ICALP is the top Theory of CS Conference in Europe). Members of our team are frequently visiting the Research Institute CTI in Greece where there is a team on Sensor Networks which provides motivation for our models and we provide feedback with respect to our findings. The team there is led by Prof. S. Nikoletseas. Members of our team have also visited a major research place in Berlin, namely the research group led by Prof. R. Niedermeier at the TU Berlin. |
| Sectors | Digital/Communication/Information Technologies (including Software) Transport |
| Description | Co-organizer of the prestigious Dagstuhl Seminar 21171 "Temporal Graphs: Structure, Algorithms, Applications", Dagstuhl, Germany, 25-30 April 2021 |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Professional Practitioners |
| Results and Impact | In this one-week Dagstuhl seminar, where we invited more than 90 researchers internationally, recent advances in the area of temporal graphs will be presented and discussed, as well as some of the current key challenges will be highlighted. Altogether, we face the challenge to better understand the many facets of computational complexity which are experienced for temporal graphs. The workshop aims to address that challenge. As this research area grows and broadens internationally, our aim is to bring together people from the various theoretical and practical sub-communities of temporal graphs in order to establish new and to strengthen existing links between these communities. Due to the pandemic, this event will be held in a hybrid-mode, i.e. some participants will be on site in Dagstuhl while the other participants will join online. |
| Year(s) Of Engagement Activity | 2021 |
| URL | https://www.dagstuhl.de/en/program/calendar/semhp/?semnr=21171 |
| Description | ICALP 2018 Workshop on Algorithmic Aspects of Temporal Graphs |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Professional Practitioners |
| Results and Impact | The workshop was held in July 2018 and has accompanied the International Colloquium on Automata, Languages and Programming (ICALP), one of the main international conferences covering all aspects of theoretical computer science. In this full-day workshop, recent advances in the area of temporal graphs were presented, as well as some of the key challenges were highlighted. The workshop was successful we had 11 speakers and approximately 30 attendees. During the discussion at the end of the workshop, the participants encouraged us to continue organizing this into a series of workshops. |
| Year(s) Of Engagement Activity | 2018 |
| URL | http://community.dur.ac.uk/george.mertzios/Workshops/ICALP-18-Satellite/Temporal-Graphs-ICALP-2018.h... |
| Description | ICALP 2019 Workshop on Algorithmic Aspects of Temporal Graphs II |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Professional Practitioners |
| Results and Impact | The workshop was held in July 2019 and has accompanied the International Colloquium on Automata, Languages and Programming (ICALP), one of the main international conferences covering all aspects of theoretical computer science. In this one-day workshop, recent advances in the area of temporal / dynamically changing graphs were presented, as well as some of the key challenges were highlighted. As this research area grows and broadens, our aim was to bring together people from theoretical and practical communities of temporal graphs in order to establish new and strengthen existing links between these communities. We had more attendees than in the previous year and we have successfully reached a broad audience attending the main conference. |
| Year(s) Of Engagement Activity | 2018,2019 |
| URL | https://mertzios.net/Workshops/ICALP-19-Satellite/Temporal-Graphs-ICALP-2019.html |
| Description | ICALP 2020 Workshop on Algorithmic Aspects of Temporal Graphs III |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Professional Practitioners |
| Results and Impact | The workshop was held in July 2020 and has accompanied the International Colloquium on Automata, Languages and Programming (ICALP), which is one of the main international conferences covering all aspects of theoretical computer science. In this one-day workshop, recent advances in the area of temporal / dynamically changing graphs were presented, as well as some of the key challenges were highlighted. As this research area grows and broadens, our aim was to bring together people from theoretical and practical communities of temporal graphs in order to establish new and strengthen existing links between these communities. Due to the pandemic, the workshop was a fully-online event and therefore we could attract many more participants from all over the world. During this workshop we managed to successfully reach a broader audience, compared to both previous years 2018 and 2019 when we organized an one-day ICALP workshop on the same topic. |
| Year(s) Of Engagement Activity | 2018,2019,2020 |
| URL | https://mertzios.net/Workshops/ICALP-20-Satellite/Temporal-Graphs-ICALP-2020.html |
| Description | ICALP 2021 Workshop on Algorithmic Aspects of Temporal Graphs IV |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Professional Practitioners |
| Results and Impact | The workshop was held in July 2021 and is planned to accompany the International Colloquium on Automata, Languages and Programming (ICALP), which is one of the main international conferences covering all aspects of theoretical computer science. In this one-day workshop, recent advances in the area of temporal / dynamically changing graphs have been presented, as well as some of the key challenges have been highlighted. As this research area grows and broadens, our aim was 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 year, due to the pandemic, the workshop was a fully-online event and therefore we managed to attract many more participants from all over the world. As we expected, the workshop successfully reached a broad audience, continuing the tradition we created in the previous years 2018, 2019 and 2020 when we organized an one-day ICALP workshop on the same topic. |
| Year(s) Of Engagement Activity | 2018,2019,2020,2021 |
| URL | https://mertzios.net/Workshops/ICALP-21-Satellite/Temporal-Graphs-ICALP-2021.html |
| Description | ICALP 2022 Workshop on Algorithmic Aspects of Temporal Graphs V |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Professional Practitioners |
| Results and Impact | The workshop will be held in July 2022 and is planned to accompany the International Colloquium on Automata, Languages and Programming (ICALP), which is one of the main international conferences covering all aspects of theoretical computer science. 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 year, due to the pandemic, the workshop will be a hybrid event and therefore we aim to attract many online participants from all over the world. We are not yet aware of the numbers of registered attendees yet, but we expect the workshop to successfully reach a broad audience, continuing the tradition we created in the previous years 2018-2021 when we organized an one-day ICALP workshop on the same topic. |
| Year(s) Of Engagement Activity | 2018,2019,2020,2021,2022 |
| URL | https://mertzios.net/Workshops/ICALP-22-Satellite/Temporal-Graphs-ICALP-2022.html |
| Description | ICALP 2023 Workshop on Algorithmic Aspects of Temporal Graphs VI |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Professional Practitioners |
| Results and Impact | The workshop was held in July 2023 and has accompanied the International Colloquium on Automata, Languages and Programming (ICALP), which is one of the main international conferences covering all aspects of theoretical computer science. In this one-day workshop, recent advances in the area of temporal / dynamically changing graphs have been presented, as well as some of the key challenges have been highlighted. As this research area grows and broadens, our aim was 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 year, the first time after the pandemic, the workshop was an in-person event. The workshop has successfully reached a broad audience, continuing the tradition we created in the previous years 2018-2022 when we organized an one-day ICALP workshop on the same topic. This series of ICALP satellite workshops has been established in the recent years and is a point of reference for international research on temporal networks. |
| Year(s) Of Engagement Activity | 2018,2019,2020,2021,2022,2023 |
| URL | https://mertzios.net/Workshops/ICALP-23-Satellite/Temporal-Graphs-ICALP-2023.html |
| Description | ICALP 2024 Workshop on Algorithmic Aspects of Temporal Graphs VII |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Professional Practitioners |
| Results and Impact | The workshop was held in July 2024 and has accompanied the International Colloquium on Automata, Languages and Programming (ICALP), which is one of the main international conferences covering all aspects of theoretical computer science. In this one-day workshop, recent advances in the area of temporal / dynamically changing graphs have been presented, as well as some of the key challenges have been highlighted. As this research area grows and broadens, our aim was 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 year the workshop was a hybrid event. The workshop has successfully reached a broad audience, continuing the tradition we created in the previous years 2018-2023 when we organized an one-day ICALP workshop on the same topic. This series of ICALP satellite workshops has been established in the recent years and is a point of reference for international research on temporal networks. |
| Year(s) Of Engagement Activity | 2018,2019,2020,2021,2022,2023,2024 |
| URL | https://mertzios.net/Workshops/ICALP-24-Satellite/Temporal-Graphs-ICALP-2024.html |
| Description | Initiation of the series of Symposia on Algorithmic Foundations of Dynamic Networks (SAND) |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Professional Practitioners |
| Results and Impact | The members of our team played an important role in co-creating in 2022 the new series of Symposia, called "Symposium on Algorithmic Foundations of Dynamic Networks (SAND)" whose topic is broadly focused on fundamental research on computing in dynamic networks. As a result of this involvement of our team, we are both included in the Advisory Board of SAND, and each year we are in the Programme Committee (PC). In addition, Paul Spirakis has been an invited speaker during the 1st SAND in 2022. |
| Year(s) Of Engagement Activity | 2022 |
| URL | https://2022.sand-conf.org/ |
| Description | Invited Speaker - 48th International Symposium on Mathematical Foundations of Computer Science (MFCS) |
| Form Of Engagement Activity | A talk or presentation |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Professional Practitioners |
| Results and Impact | I was an invited speaker at the conference. |
| Year(s) Of Engagement Activity | 2023 |
| URL | https://mfcs2023.labri.fr/#invited |
| Description | PC member - 13th International Conference on Algorithms and Complexity (CIAC) |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Professional Practitioners |
| Results and Impact | I was a member of the Program Committee at the conference. |
| Year(s) Of Engagement Activity | 2023 |
| URL | https://easyconferences.eu/ciac2023/ |
| Description | PC member - 24th International Conference On Distributed Computing And Networking (ICDCN) |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Professional Practitioners |
| Results and Impact | I was a member of the Program Committee at the conference. |
| Year(s) Of Engagement Activity | 2023 |
| URL | https://cse.iitkgp.ac.in/conf/ICDCN23/index.html |
| Description | PC member - 25th International Conference On Distributed Computing And Networking (ICDCN) |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Professional Practitioners |
| Results and Impact | I was a member of the Program Committee at the conference. |
| Year(s) Of Engagement Activity | 2024 |
| URL | https://cse.iitm.ac.in/~icdcn2024/ |
| Description | PC member - 27th Pan-Hellenic Conference on Progress in Computing and Informatics (PCI) |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Professional Practitioners |
| Results and Impact | I was a member of the Program Committee at the conference. |
| Year(s) Of Engagement Activity | 2023 |
| URL | https://pci2023.uth.gr/ |
| Description | PC member - 34th International Workshop on Combinatorial Algorithms (IWOCA) |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Professional Practitioners |
| Results and Impact | I was a member of the Program Committee at the conference. |
| Year(s) Of Engagement Activity | 2023 |
| URL | https://iwoca2023.csie.ncku.edu.tw/ |
| Description | PC member - 49th International Symposium on Mathematical Foundations of Computer Science (MFCS) |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Professional Practitioners |
| Results and Impact | I am a member of the Program Committee at the conference. |
| Year(s) Of Engagement Activity | 2024 |
| URL | http://www.mfcs.sk/ |
| Description | PC member - International Symposium on Cyber Security, Cryptology and Machine Learning (CSCML) |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Professional Practitioners |
| Results and Impact | I was a member of the Program Committee at the conference. |
| Year(s) Of Engagement Activity | 2023 |
| URL | https://www.cscml.org/ |
| Description | PC members and chair - SAND 2023 - 2nd Symposium on Algorithmic Foundations of Dynamic Networks |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Professional Practitioners |
| Results and Impact | As both members of our team co-founded the series of the SAND symposia in 2022, we are both included both in the Advisory Board of SAND and in the Programme Committee (PC) of SAND 2023. In addition, Paul Spirakis is the PC chair at the 2nd SAND in 2023. |
| Year(s) Of Engagement Activity | 2023 |
| URL | https://sand-conf.org/ |
| Description | PC members and chair - SAND 2024 - 3nd Symposium on Algorithmic Foundations of Dynamic Networks |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | International |
| Primary Audience | Professional Practitioners |
| Results and Impact | As both members of our team co-founded the series of the SAND symposia in 2022, we are both included both in the Advisory Board of SAND and in the Programme Committee (PC) of SAND 2024. |
| Year(s) Of Engagement Activity | 2024 |
| URL | https://sand-conf.org/ |