Interference-free walks in time: Temporally disjoint paths (2022)
Journal Article
Klobas, N., Mertzios, G., Molter, H., Niedermeier, R., & Zschoche, P. (2022). Interference-free walks in time: Temporally disjoint paths. Autonomous Agents and Multi-Agent Systems, 37, Article 1. https://doi.org/10.1007/s10458-022-09583-5

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 computing optimum labelings for temporal connectivity (2022)
Conference Proceeding
Klobas, N., Mertzios, G., Molter, H., & Spirakis, P. (2022). The complexity of computing optimum labelings for temporal connectivity. . https://doi.org/10.4230/lipics.mfcs.2022.62

A graph is temporally connected if there exists a strict temporal path, i.e., a path whose edges have strictly increasing labels, from every vertex u to every other vertex v. In this paper we study temporal design problems for undirected temporally c... Read More about The complexity of computing optimum labelings for temporal connectivity.

The complexity of temporal vertex cover in small-degree graphs (2022)
Conference Proceeding
Hamm, T., Klobas, N., Mertzios, G., & Spirakis, P. (2022). The complexity of temporal vertex cover in small-degree graphs. . https://doi.org/10.1609/aaai.v36i9.21259

Temporal graphs naturally model graphs whose underlying topology changes over time. Recently, the problems Temporal Vertex Cover (or TVC) and Sliding-Window Temporal Vertex Cover (or ∆- TVC for time-windows of a fixed-length ∆) have been established... Read More about The complexity of temporal vertex cover in small-degree graphs.

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.