Interference-free walks in time: temporally disjoint paths (2021)
Conference Proceeding
Klobas, N., Mertzios, G., Molter, H., Niedermeier, R., & Zschoche, P. (2021). Interference-free walks in time: temporally disjoint paths. . https://doi.org/10.24963/ijcai.2021/563

We investigate the computational complexity of finding temporally disjoint paths or walks in temporal graphs. There, the edge set changes over discrete time steps and a temporal path (resp. walk) uses edges that appear at monotonically increasing tim... Read More about Interference-free walks in time: temporally disjoint paths.

The complexity of transitively orienting temporal graphs (2021)
Conference Proceeding
Mertzios, G., Molter, H., Renken, M., Spirakis, P., & Zschoche, P. (2021). The complexity of transitively orienting temporal graphs. In F. Bonchi, & S. J. Puglisi (Eds.), . https://doi.org/10.4230/lipics.mfcs.2021.75

In a temporal network with discrete time-labels on its edges, entities and information can only “flow” along sequences of edges whose time-labels are non-decreasing (resp. increasing), i.e. along temporal (resp. strict temporal) paths. Nevertheless,... Read More about The complexity of transitively orienting temporal graphs.

Equitable scheduling on a single machine (2021)
Conference Proceeding
Heeger, K., Hermelin, D., Mertzios, G., Molter, H., Niedermeier, R., & Shabtay, D. (2021). Equitable scheduling on a single machine. . https://doi.org/10.1609/aaai.v35i13.17404

We introduce a natural but seemingly yet unstudied generalization of the problem of scheduling jobs on a single machine so as to minimize the number of tardy jobs. Our generalization lies in simultaneously considering several instances of the problem... Read More about Equitable scheduling on a single machine.

The temporal explorer who returns to the base (2021)
Journal Article
Akrida, E., Mertzios, G., Spirakis, P., & Raptopoulos, C. (2021). The temporal explorer who returns to the base. Journal of Computer and System Sciences, 120, 179-193. https://doi.org/10.1016/j.jcss.2021.04.001

We study here the problem of exploring a temporal graph when the underlying graph is a star. The aim of the exploration problem in a temporal star is finding a temporal walk which starts and finishes at the center of the star, and visits all leaves.... Read More about The temporal explorer who returns to the base.

Sliding window temporal graph coloring (2021)
Journal Article
Mertzios, G., Molter, H., & Zamaraev, V. (2021). Sliding window temporal graph coloring. Journal of Computer and System Sciences, 120, 97-115. https://doi.org/10.1016/j.jcss.2021.03.005

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.

Deleting edges to restrict the size of an epidemic in temporal networks (2021)
Journal Article
Enright, J., Meeks, K., Mertzios, G., & Zamaraev, V. (2021). Deleting edges to restrict the size of an epidemic in temporal networks. Journal of Computer and System Sciences, 119, 60-77. https://doi.org/10.1016/j.jcss.2021.01.007

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