Outputs (7)

The complexity of computing optimum labelings for temporal connectivity (2024)
Journal Article
Klobas, N., Mertzios, G., Molter, H., & Spirakis, P. (2024). The complexity of computing optimum labelings for temporal connectivity. Journal of Computer and System Sciences, 146, Article 103564. https://doi.org/10.1016/j.jcss.2024.103564

A graph is temporally connected if a strict temporal path exists from every vertex u to every other vertex v. This paper studies temporal design problems for undirected temporally connected graphs. Given a connected undirected graph G, the goal is to... Read More about The complexity of computing optimum labelings for temporal connectivity.

Temporal Graph Realization from Fastest Paths (2024)
Presentation / Conference Contribution
Klobas, N., Mertzios, G., Molter, H., & Spirakis, P. (2024, June). Temporal Graph Realization from Fastest Paths. Presented at 3rd Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2024, Patras, Greece

In this paper we initiate the study of the temporal graph realization problem with respect to the fastest path durations among its vertices, while we focus on periodic temporal graphs. Given an n × n matrix D and a Δ ∈ ℕ, the goal is to construct a Δ... Read More about Temporal Graph Realization from Fastest Paths.

Sliding into the Future: Investigating Sliding Windows in Temporal Graphs (2023)
Presentation / Conference Contribution
Klobas, N., Mertzios, G. B., & Spirakis, P. G. (2023, August). Sliding into the Future: Investigating Sliding Windows in Temporal Graphs. Presented at 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), Bordeaux, France

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)
Presentation / Conference Contribution
Klobas, N., Mertzios, G., Molter, H., & Spirakis, P. (2022, August). The complexity of computing optimum labelings for temporal connectivity. Presented at 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), Vienna, Austria

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)
Presentation / Conference Contribution
Hamm, T., Klobas, N., Mertzios, G., & Spirakis, P. (2023, February). The complexity of temporal vertex cover in small-degree graphs. Presented at 36th AAAI Conference on Artificial Intelligence (AAAI 2022), Vancouver, BC

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)
Presentation / Conference Contribution
Klobas, N., Mertzios, G., Molter, H., Niedermeier, R., & Zschoche, P. (2021, August). Interference-free walks in time: temporally disjoint paths. Presented at 30th International Joint Conference on Artificial Intelligence (IJCAI-21), Montreal, Quebec

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.