Search Results

Documents authored by Reinhardt, Klaus

Document
DOI: 10.4230/LIPIcs.SAND.2026.19
Minimize the Sum of Waiting Times in Periodic Temporal Trees

Authors: Julia Meusel, Nils Morawietz, Matthias Müller-Hannemann, and Klaus Reinhardt

Published in: LIPIcs, Volume 373, 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)

Abstract
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.
Cite as

Julia Meusel, Nils Morawietz, Matthias Müller-Hannemann, and Klaus Reinhardt. Minimize the Sum of Waiting Times in Periodic Temporal Trees. In 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 373, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{meusel_et_al:LIPIcs.SAND.2026.19,
  author =	{Meusel, Julia and Morawietz, Nils and M\"{u}ller-Hannemann, Matthias and Reinhardt, Klaus},
  title =	{{Minimize the Sum of Waiting Times in Periodic Temporal Trees}},
  booktitle =	{5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)},
  pages =	{19:1--19:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-427-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{373},
  editor =	{Mertzios, George B. and Richa, Andr\'{e}a W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2026.19},
  URN =		{urn:nbn:de:0030-drops-262531},
  doi =		{10.4230/LIPIcs.SAND.2026.19},
  annote =	{Keywords: graph realization, fastest temporal path, periodic temporal graphs}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.SAND.2026.21
Brief Announcement: Revisiting the Realizability of Periodic Temporal Graphs with Bounded Stretch

Authors: Julia Meusel, Nils Morawietz, Matthias Müller-Hannemann, and Klaus Reinhardt

Published in: LIPIcs, Volume 373, 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)

Abstract
In this work, we revisit Stretched Periodic Temporal Graph Realization (STGR) which was recently introduced by Mertzios et al. [MFCS 2025]. Here, the input consists of an undirected graph G = (V,E), a period Δ, and a rational number α ≥ 1, and the question is, whether there is a labeling λ: E → [0,Δ-1], such that the stretch is at most α in the Δ-periodic temporal graph (G,λ), that is, the temporal graph, where for each c ∈ ℕ and each edge e, e appears at time c⋅ Δ + i if and only if λ(e) = i. The stretch of (G,λ) is the maximum stretch between any vertex pair (u,v) in (G,λ), where the stretch of a vertex pair (u,v) is defined as the duration of a fastest temporal path from u to v in (G,λ) divided by the distance between these vertices in the underlying graph. We complete the complexity picture for STGR with respect to Δ by investigating the open case of Δ = 2. It turns out that STGR is NP-hard for each Δ > 1. Moreover, we also answer the open question by Mertzios et al. on whether there are graphs for which the smallest possible stretch is larger than (Δ+1)/2. We show not only that such graphs exist, but also that it remains NP-hard to decide whether the optimal stretch is at most (Δ+1)/2. Our hardness results for Δ = 2 also imply hardness for Δ = 2 for the Fastest Periodic Temporal Graph Realization problem that was introduced by Klobas et al. [TCS 2025]. Finally, we show the existence of classes of graphs with small and large stretch.
Cite as

Julia Meusel, Nils Morawietz, Matthias Müller-Hannemann, and Klaus Reinhardt. Brief Announcement: Revisiting the Realizability of Periodic Temporal Graphs with Bounded Stretch. In 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 373, pp. 21:1-21:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{meusel_et_al:LIPIcs.SAND.2026.21,
  author =	{Meusel, Julia and Morawietz, Nils and M\"{u}ller-Hannemann, Matthias and Reinhardt, Klaus},
  title =	{{Brief Announcement: Revisiting the Realizability of Periodic Temporal Graphs with Bounded Stretch}},
  booktitle =	{5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2026)},
  pages =	{21:1--21:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-427-7},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{373},
  editor =	{Mertzios, George B. and Richa, Andr\'{e}a W.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2026.21},
  URN =		{urn:nbn:de:0030-drops-262556},
  doi =		{10.4230/LIPIcs.SAND.2026.21},
  annote =	{Keywords: fastest temporal path, periodic temporal graphs, graph realization}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2025.3
Directed Temporal Tree Realization for Periodic Public Transport: Easy and Hard Cases

Authors: Julia Meusel, Matthias Müller-Hannemann, and Klaus Reinhardt

Published in: OASIcs, Volume 137, 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)

Abstract
We study the complexity of the directed periodic temporal graph realization problem. This work is motivated by the design of periodic schedules in public transport with constraints on the quality of service. Namely, we require that the fastest path between (important) pairs of vertices is upper bounded by a specified maximum duration, encoded in an upper distance matrix D. While previous work has considered the undirected version of the problem, the application in public transport schedule design requires the flexibility to assign different departure times to the two directions of an edge. A problem instance can only be feasible if all values of the distance matrix are at least shortest path distances. However, the task of realizing exact fastest path distances in a periodic temporal graph is often too restrictive. Therefore, we introduce a minimum slack parameter k that describes a lower bound on the maximum allowed waiting time on each path. We concentrate on tree topologies and provide a full characterization of the complexity landscape with respect to the period Δ and the minimum slack parameter k, showing a sharp threshold between NP-complete cases and cases which are always realizable. We also provide hardness results for the special case of period Δ = 2 for general directed and undirected graphs.
Cite as

Julia Meusel, Matthias Müller-Hannemann, and Klaus Reinhardt. Directed Temporal Tree Realization for Periodic Public Transport: Easy and Hard Cases. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 3:1-3:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{meusel_et_al:OASIcs.ATMOS.2025.3,
  author =	{Meusel, Julia and M\"{u}ller-Hannemann, Matthias and Reinhardt, Klaus},
  title =	{{Directed Temporal Tree Realization for Periodic Public Transport: Easy and Hard Cases}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{3:1--3:22},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-404-8},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{137},
  editor =	{Sauer, Jonas and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2025.3},
  URN =		{urn:nbn:de:0030-drops-247594},
  doi =		{10.4230/OASIcs.ATMOS.2025.3},
  annote =	{Keywords: Periodic timetabling, service quality, temporal graph, graph realization, complexity}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.SAND.2025.21
Brief Announcement: Directed Temporal Tree Realization for Periodic Public Transport: Easy and Hard Cases

Authors: Julia Meusel, Matthias Müller-Hannemann, and Klaus Reinhardt

Published in: LIPIcs, Volume 330, 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)

Abstract
We study the complexity of the directed periodic temporal graph realization problem. This work is motivated by the design of periodic schedules in public transport with constraints on the quality of service. Namely, we require that the fastest path between (important) pairs of vertices is upper bounded by a specified maximum duration, encoded in an upper distance matrix D. While previous work has considered the undirected version of the problem, the application in public transport schedule design requires the flexibility to assign different departure times to the two directions of an edge. A problem instance can only be feasible if all values of the distance matrix are at least shortest path distances. However, the task of realizing exact fastest path distances in a periodic temporal graph is often too restrictive. Therefore, we introduce a minimum slack parameter k that describes a lower bound on the maximum allowed waiting time on each path. We concentrate on tree topologies and provide a full characterization of the complexity landscape with respect to the period Δ and the minimum slack parameter k, showing a sharp threshold between NP-complete cases and cases which are always realizable. We also provide hardness results for the special case of period Δ = 2 for general directed and undirected graphs.
Cite as

Julia Meusel, Matthias Müller-Hannemann, and Klaus Reinhardt. Brief Announcement: Directed Temporal Tree Realization for Periodic Public Transport: Easy and Hard Cases. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 21:1-21:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{meusel_et_al:LIPIcs.SAND.2025.21,
  author =	{Meusel, Julia and M\"{u}ller-Hannemann, Matthias and Reinhardt, Klaus},
  title =	{{Brief Announcement: Directed Temporal Tree Realization for Periodic Public Transport: Easy and Hard Cases}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{21:1--21:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-368-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{330},
  editor =	{Meeks, Kitty and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2025.21},
  URN =		{urn:nbn:de:0030-drops-230747},
  doi =		{10.4230/LIPIcs.SAND.2025.21},
  annote =	{Keywords: Temporal graph, fastest temporal path, graph realization, periodic scheduling}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact