Outputs (5)

Deleting edges to restrict the size of an epidemic in temporal networks (2019)
Presentation / Conference Contribution
Enright, J., Meeks, K., Mertzios, G., & Zamaraev, V. (2019, August). Deleting edges to restrict the size of an epidemic in temporal networks. Presented at 44th International Symposium on Mathematical Foundations of Computer Science (MFCS), Aachen, Germany

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)
Presentation / Conference Contribution
Akrida, E. C., Mertzios, G. B., Nikoletseas, S., Christoforos, R., Spirakis, P. G., & Zamaraev, V. (2019, July). How fast can we reach a target vertex in stochastic temporal graphs?. Presented at 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), Patras, Greece

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)
Presentation / Conference Contribution
Mertzios, G., Molter, H., & Zamaraev, V. (2023, January). Sliding Window Temporal Graph Coloring. Presented at 33rd AAAI Conference on Artificial Intelligence (AAAI 2019)., Honolulu, Hawaii, USA

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)
Presentation / Conference Contribution
Akrida, E., Mertzios, G., & Spirakis, P. (2019, December). The temporal explorer who returns to the base. Presented at 11th International Conference on Algorithms and Complexity (CIAC 2019), Rome, Italy

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.