2026-09-08T02:21:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26253 2026-09-05T19:39:24Z ddc:004 open_access

Minimize the Sum of Waiting Times in Periodic Temporal Trees Meusel, Julia Morawietz, Nils Müller-Hannemann, Matthias Reinhardt, Klaus graph realization fastest temporal path periodic temporal graphs We introduce and analyze the problem of finding a Δ-labeling λ for an undirected tree G = (V,E), such that the sum of overall waiting times of fastest paths between all vertex pairs is minimized in the Δ-periodic temporal graph (G,λ). That is, we aim to minimize ∑_{(u,v) ∈ V×V} (dur(u,v)-dist(u,v)), where dur(u,v) is the duration of a fastest temporal path from u to v and dist(u,v) is the length of the shortest path between u and v in G. We show that this objective function essentially boils down to a known problem about partitioning a set of natural numbers that has applications in scheduling. From that problem we lift and adapt several upper and lower bounds for our problem. For example, we show that the problem admits an EPTAS, that is, an algorithm that can compute a (1+ε)-approximation to our problem in time f(1/ε) ⋅ n^𝒪(1) for each ε > 0. To the best of our knowledge, this is the first example of an efficient approximation algorithm for a temporal graph realization problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Julia Meusel and Nils Morawietz and Matthias Müller-Hannemann and Klaus Reinhardt 2026 Is Part Of LIPIcs, Volume 373, 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SAND.2026.19 urn:nbn:de:0030-drops-262531 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2026.19 eng https://creativecommons.org/licenses/by/4.0/legalcode