Deleting edges to restrict the size of an epidemic in temporal networks (2019)
Conference Proceeding
Enright, J., Meeks, K., Mertzios, G., & Zamaraev, V. (2019). Deleting edges to restrict the size of an epidemic in temporal networks. In P. Rossmanith, P. Heggernes, & J. Katoen (Eds.), 44th International Symposium on Mathematical Foundations of Computer Science (57:1-57:15). https://doi.org/10.4230/lipics.mfcs.2019.57

Spreading processes on graphs are a natural model for a wide variety of real-world phenomena, including information or behaviour spread over social networks, biological diseases spreading over contact or trade networks, and the potential flow of good... Read More about Deleting edges to restrict the size of an epidemic in temporal networks.

Temporal vertex cover with a sliding time window (2019)
Journal Article
Akrida, E., Mertzios, G., Spirakis, P., & Zamaraev, V. (2020). Temporal vertex cover with a sliding time window. Journal of Computer and System Sciences, 107, 108-123. https://doi.org/10.1016/j.jcss.2019.08.002

Modern, inherently dynamic systems are usually characterized by a network structure which is subject to discrete changes over time. Given a static underlying graph, a temporal graph can be represented via an assignment of a set of integer time-labels... Read More about Temporal vertex cover with a sliding time window.

How fast can we reach a target vertex in stochastic temporal graphs? (2019)
Conference Proceeding
Akrida, E. C., Mertzios, G. B., Nikoletseas, S., Christoforos, R., Spirakis, P. G., & Zamaraev, V. (2019). How fast can we reach a target vertex in stochastic temporal graphs?. In C. Baier, I. Chatzigiannakis, P. Flocchini, & S. Leonardi (Eds.), 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) (131:1-131:14). https://doi.org/10.4230/lipics.icalp.2019.131

Temporal graphs are used to abstractly model real-life networks that are inherently dynamic in nature, in the sense that the network structure undergoes discrete changes over time. Given a static underlying graph G=(V,E), a temporal graph on G is a s... Read More about How fast can we reach a target vertex in stochastic temporal graphs?.

Sliding Window Temporal Graph Coloring (2019)
Conference Proceeding
Mertzios, G., Molter, H., & Zamaraev, V. (2019). Sliding Window Temporal Graph Coloring. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence (7667-7674). https://doi.org/10.1609/aaai.v33i01.33017667

Graph coloring is one of the most famous computational problems with applications in a wide range of areas such as planning and scheduling, resource allocation, and pattern matching. So far coloring problems are mostly studied on static graphs, which... Read More about Sliding Window Temporal Graph Coloring.

The temporal explorer who returns to the base (2019)
Conference Proceeding
Akrida, E., Mertzios, G., & Spirakis, P. (2019). The temporal explorer who returns to the base. In P. Heggernes (Ed.), Algorithms and Complexity (CIAC 2019); 11th International Conference, CIAC 2019, Rome, Italy, May 27–29, 2019 ; proceedings (13-24). https://doi.org/10.1007/978-3-030-17402-6_2

In this paper we study the problem of exploring a temporal graph (i.e. a graph that changes over time), in the fundamental case where the underlying static graph is a star on n vertices. The aim of the exploration problem in a temporal star is to fin... Read More about The temporal explorer who returns to the base.