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
A. Deligkas
(2018)
Approximating the Existential Theory of the Reals
A. Deligkas
(2017)
Binary Search in Graphs Revisited
A. Deligkas
(2021)
Walrasian Equilibria in Markets with Small Demands
Akrida E
(2019)
Temporal flows in temporal networks
in Journal of Computer and System Sciences
Akrida E
(2021)
The temporal explorer who returns to the base
in Journal of Computer and System Sciences
Akrida E
(2020)
How fast can we reach a target vertex in stochastic temporal graphs?
in Journal of Computer and System Sciences
Akrida E
(2020)
Temporal vertex cover with a sliding time window
in Journal of Computer and System Sciences
Akrida E
(2021)
Connected Subgraph Defense Games
in Algorithmica
| 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 | 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 will be held in July 2023 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, the first time after the pandemic, the workshop will be an in-person event. 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-2022 when we organized an one-day ICALP workshop on the same topic. This series of ICALP satellite workshops have 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 | 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 | 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/ |