Outputs (5)

The complexity of growing a graph (2022)
Presentation / Conference Contribution
Mertzios, G., Michail, O., Skretas, G., Spirakis, P., & Theofilatos, M. (2022, September). The complexity of growing a graph. Presented at 18th International Symposium on Algorithmics of Wireless Networks (ALGOSENSORS 2022), Potsdam, Germany

We study a new algorithmic process of graph growth. The process starts from a single initial vertex u0 and operates in discrete timesteps, called slots. In every slot t ≥ 1, the process updates the current graph instance to generate the next graph in... Read More about The complexity of growing a graph.

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.

Equitable scheduling on a single machine (2022)
Journal Article
Heeger, K., Hermelin, D., Mertzios, G., Molter, H., Niedermeier, R., & Shabtay, D. (2023). Equitable scheduling on a single machine. Journal of Scheduling, 26(2), 209-225. https://doi.org/10.1007/s10951-022-00754-6

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

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.