8 Search Results for "Spooner, Jakob T."

Document
DOI: 10.4230/LIPIcs.ISAAC.2025.27
Simple, Strict, Proper, and Directed: Comparing Reachability in Directed and Undirected Temporal Graphs

Authors: Michelle Döring

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
Temporal graphs model networks whose connections are available only at specific points in time. Several definitional subtleties - whether paths must follow strictly increasing time labels (strict vs. non-strict), whether adjacent edges cannot appear simultaneously (proper), and whether edges are forbidden to appear multiple times (simple) - give rise to different temporal graph settings. These distinctions directly impact the definition of temporal reachability, a core concept in temporal graph theory. Casteigts, Corsini, and Sarkar [TCS24] introduced a framework of equivalence notions to compare the expressive power of these settings focusing solely on undirected temporal graphs. In this work, we extend their framework to include the fundamental dimension of directed vs. undirected. Our contribution is three-fold. We (1) complete the undirected hierarchy by resolving the two open questions from [TCS24], (2) fully characterize the hierarchy of the directed settings, and (3) compare the directed and undirected settings, showing that directed temporal graphs are strictly more expressive than undirected temporal graphs in terms of reachability. Our structural results highlight both the limitations and strengths of various temporal graph settings - for example, directed + strict + simple graphs can realize every possible reachability graph, while directed + proper graphs necessarily induce at least one transitive reachability on each directed cycle. We also provide transformation procedures between temporal settings offering practical tools for transferring algorithms and hardness results across models.
Cite as

Michelle Döring. Simple, Strict, Proper, and Directed: Comparing Reachability in Directed and Undirected Temporal Graphs. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 27:1-27:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{doring:LIPIcs.ISAAC.2025.27,
  author =	{D\"{o}ring, Michelle},
  title =	{{Simple, Strict, Proper, and Directed: Comparing Reachability in Directed and Undirected Temporal Graphs}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{27:1--27:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.27},
  URN =		{urn:nbn:de:0030-drops-249353},
  doi =		{10.4230/LIPIcs.ISAAC.2025.27},
  annote =	{Keywords: temporal graphs, directed graphs, temporal reachability, dynamic networks}
}
Document
DOI: 10.4230/LIPIcs.DISC.2025.41
Natural Calamities Demand More Rescuers: Exploring Connectivity Time Dynamic Graphs

Authors: Ashish Saxena and Kaushik Mondal

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract
We study the exploration problem by mobile agents in Connectivity Time dynamic graphs. The Connectivity Time model was introduced by Michail et al. [JPDC 2014] and is arguably one of the weakest dynamic graph connectivity models. We prove that exploration is impossible in such graphs using ((n-1)(n-2))/2 mobile agents starting from an arbitrary initial configuration, even when agents have full knowledge of system parameters, global communication, full visibility, and infinite memory. We then present an exploration algorithm that uses ((n-1)(n-2))/2 + 1 agents equipped with global communication, 1-hop visibility and O(log n) memory.
Cite as

Ashish Saxena and Kaushik Mondal. Natural Calamities Demand More Rescuers: Exploring Connectivity Time Dynamic Graphs. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 41:1-41:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{saxena_et_al:LIPIcs.DISC.2025.41,
  author =	{Saxena, Ashish and Mondal, Kaushik},
  title =	{{Natural Calamities Demand More Rescuers: Exploring Connectivity Time Dynamic Graphs}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{41:1--41:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.41},
  URN =		{urn:nbn:de:0030-drops-248585},
  doi =		{10.4230/LIPIcs.DISC.2025.41},
  annote =	{Keywords: Mobile agents, Anonymous graphs, Exploration, Dynamic graphs, Deterministic algorithm}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.75
Temporal Graph Realization with Bounded Stretch

Authors: George B. Mertzios, Hendrik Molter, Nils Morawietz, and Paul G. Spirakis

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
A periodic temporal graph, in its simplest form, is a graph in which every edge appears exactly once in the first Δ time steps, and then it reappears recurrently every Δ time steps, where Δ is a given period length. This model offers a natural abstraction of transportation networks where each transportation link connects two destinations periodically. From a network design perspective, a crucial task is to assign the time-labels on the edges in a way that optimizes some criterion. In this paper we introduce a very natural optimality criterion that captures how the temporal distances of all vertex pairs are "stretched", compared to their physical distances, i.e. their distances in the underlying static (non-temporal) graph. Given a static graph G, the task is to assign to each edge one time-label between 1 and Δ such that, in the resulting periodic temporal graph with period Δ, the duration of the fastest temporal path from any vertex u to any other vertex v is at most α times the distance between u and v in G. Here, the value of α measures how much the shortest paths are allowed to be stretched once we assign the periodic time-labels. Our results span three different directions: First, we provide a series of approximation and NP-hardness results. Second, we provide approximation and fixed-parameter algorithms. Among them, we provide a simple polynomial-time algorithm (the radius-algorithm) which always guarantees an approximation strictly smaller than Δ, and which also computes the optimum stretch in some cases. Third, we consider a parameterized local search extension of the problem where we are given the temporal labeling of the graph, but we are allowed to change the time-labels of at most k edges; for this problem we prove that it is W[2]-hard but admits an XP algorithm with respect to k.
Cite as

George B. Mertzios, Hendrik Molter, Nils Morawietz, and Paul G. Spirakis. Temporal Graph Realization with Bounded Stretch. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 75:1-75:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mertzios_et_al:LIPIcs.MFCS.2025.75,
  author =	{Mertzios, George B. and Molter, Hendrik and Morawietz, Nils and Spirakis, Paul G.},
  title =	{{Temporal Graph Realization with Bounded Stretch}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{75:1--75:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.75},
  URN =		{urn:nbn:de:0030-drops-241829},
  doi =		{10.4230/LIPIcs.MFCS.2025.75},
  annote =	{Keywords: Temporal graph, periodic temporal labeling, fastest temporal path, graph realization, temporal connectivity, stretch}
}
Document
DOI: 10.4230/LIPIcs.SAND.2025.12
Restless Exploration and Token Dissemination in Vertex-Permuted Temporal Graphs

Authors: Kamran Ayoubi and Lata Narayanan

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

Abstract
In the temporal graph exploration problem, an agent wishes to visit all the vertices of a temporal graph, moving at most one edge in every time step. In restless exploration, the agent is required to move in every step, and cannot wait at a vertex. We study the problem of restless exploration in vertex-permuted graphs, which are a class of temporal graphs in which the topology of the graph stays the same in every time step. In other words, in a vertex permuted temporal graph, in every step i, the graph G_i is isomorphic to the same base graph G. We give a precise characterization of graphs G such that restless exploration is possible in every vertex-permuted graph with base graph G. Our technique is based on an a characterization of networks in which there is an online distributed algorithm for restless token dissemination. Finally we describe some families of graphs in which restless exploration is always possible, and some in which it is not.
Cite as

Kamran Ayoubi and Lata Narayanan. Restless Exploration and Token Dissemination in Vertex-Permuted Temporal Graphs. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 12:1-12:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ayoubi_et_al:LIPIcs.SAND.2025.12,
  author =	{Ayoubi, Kamran and Narayanan, Lata},
  title =	{{Restless Exploration and Token Dissemination in Vertex-Permuted Temporal Graphs}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{12:1--12:17},
  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.12},
  URN =		{urn:nbn:de:0030-drops-230658},
  doi =		{10.4230/LIPIcs.SAND.2025.12},
  annote =	{Keywords: Temporal graphs, Vertex permuted graphs, Restless exploration, Periodic graphs, Token dissemination}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.SAND.2025.22
Brief Announcement: Exploring Word-Representable Temporal Graphs

Authors: Duncan Adamson

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

Abstract
Word-representable graphs are a subset of graphs that may be represented by a word w over an alphabet composed of the vertices in the graph. In such graphs, an edge exists if and only if the occurrences of the corresponding vertices alternate in the word w. We generalise this notion to temporal graphs, constructing timesteps by partitioning the word into factors (contiguous subwords) such that no factor contains more than one copy of any given symbol. With this definition, we study the problem of exploration, asking for the fastest schedule such that a given agent may explore all n vertices of the graph. We show that if the corresponding temporal graph is connected in every timestep, we may explore the graph in 2δ n timesteps, where δ is the lowest degree of any vertex in the graph. In general, we show that, for any temporal graph represented by a word of length at least n(2dn + d), with a connected underlying graph, the full graph can be explored in 2 d n timesteps, where d is the diameter of the graph.
Cite as

Duncan Adamson. Brief Announcement: Exploring Word-Representable Temporal Graphs. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 22:1-22:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{adamson:LIPIcs.SAND.2025.22,
  author =	{Adamson, Duncan},
  title =	{{Brief Announcement: Exploring Word-Representable Temporal Graphs}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{22:1--22:6},
  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.22},
  URN =		{urn:nbn:de:0030-drops-230755},
  doi =		{10.4230/LIPIcs.SAND.2025.22},
  annote =	{Keywords: Temporal Graphs, Word-Representable Graphs}
}
Document
DOI: 10.4230/LIPIcs.SAND.2022.15
Parameterized Temporal Exploration Problems

Authors: Thomas Erlebach and Jakob T. Spooner

Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

Abstract
In this paper we study the fixed-parameter tractability of the problem of deciding whether a given temporal graph 𝒢 admits a temporal walk that visits all vertices (temporal exploration) or, in some problem variants, a certain subset of the vertices. Formally, a temporal graph is a sequence 𝒢 = ⟨ G₁,..., G_L⟩ of graphs with V(G_t) = V(G) and E(G_t) ⊆ E(G) for all t ∈ [L] and some underlying graph G, and a temporal walk is a time-respecting sequence of edge-traversals. For the strict variant, in which edges must be traversed in strictly increasing timesteps, we give FPT algorithms for the problem of finding a temporal walk that visits a given set X of vertices, parameterized by |X|, and for the problem of finding a temporal walk that visits at least k distinct vertices in V, parameterized by k. For the non-strict variant, in which an arbitrary number of edges can be traversed in each timestep, we parameterize by the lifetime L of the input graph and provide an FPT algorithm for the temporal exploration problem. We also give additional FPT or W[2]-hardness results for further problem variants.
Cite as

Thomas Erlebach and Jakob T. Spooner. Parameterized Temporal Exploration Problems. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{erlebach_et_al:LIPIcs.SAND.2022.15,
  author =	{Erlebach, Thomas and Spooner, Jakob T.},
  title =	{{Parameterized Temporal Exploration Problems}},
  booktitle =	{1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
  pages =	{15:1--15:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-224-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{221},
  editor =	{Aspnes, James and Michail, Othon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.15},
  URN =		{urn:nbn:de:0030-drops-159570},
  doi =		{10.4230/LIPIcs.SAND.2022.15},
  annote =	{Keywords: Temporal graphs, fixed-parameter tractability, parameterized complexity}
}
Document
Track C: Foundations of Networks and Multi-Agent Systems: Models, Algorithms and Information Management
DOI: 10.4230/LIPIcs.ICALP.2019.141
Two Moves per Time Step Make a Difference

Authors: Thomas Erlebach, Frank Kammer, Kelin Luo, Andrej Sajenko, and Jakob T. Spooner

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
A temporal graph is a graph whose edge set can change over time. We only require that the edge set in each time step forms a connected graph. The temporal exploration problem asks for a temporal walk that starts at a given vertex, moves over at most one edge in each time step, visits all vertices, and reaches the last unvisited vertex as early as possible. We show in this paper that every temporal graph with n vertices can be explored in O(n^{1.75}) time steps provided that either the degree of the graph is bounded in each step or the temporal walk is allowed to make two moves per step. This result is interesting because it breaks the lower bound of Omega(n^2) steps that holds for the worst-case exploration time if only one move per time step is allowed and the graph in each step can have arbitrary degree. We complement this main result by a logarithmic inapproximability result and a proof that for sparse temporal graphs (i.e., temporal graphs with O(n) edges in the underlying graph) making O(1) moves per time step can improve the worst-case exploration time at most by a constant factor.
Cite as

Thomas Erlebach, Frank Kammer, Kelin Luo, Andrej Sajenko, and Jakob T. Spooner. Two Moves per Time Step Make a Difference. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 141:1-141:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{erlebach_et_al:LIPIcs.ICALP.2019.141,
  author =	{Erlebach, Thomas and Kammer, Frank and Luo, Kelin and Sajenko, Andrej and Spooner, Jakob T.},
  title =	{{Two Moves per Time Step Make a Difference}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{141:1--141:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.141},
  URN =		{urn:nbn:de:0030-drops-107176},
  doi =		{10.4230/LIPIcs.ICALP.2019.141},
  annote =	{Keywords: Temporal Graph Exploration, Algorithmic Graph Theory, NP-Complete Problem}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2018.36
Faster Exploration of Degree-Bounded Temporal Graphs

Authors: Thomas Erlebach and Jakob T. Spooner

Published in: LIPIcs, Volume 117, 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)

Abstract
A temporal graph can be viewed as a sequence of static graphs indexed by discrete time steps. The vertex set of each graph in the sequence remains the same; however, the edge sets are allowed to differ. A natural problem on temporal graphs is the Temporal Exploration problem (TEXP): given, as input, a temporal graph G of order n, we are tasked with computing an exploration schedule (i.e., a temporal walk that visits all vertices in G), such that the time step at which the walk arrives at the last unvisited vertex is minimised (we refer to this time step as the arrival time). It can be easily shown that general temporal graphs admit exploration schedules with arrival time no greater than O(n^2). Moreover, it has been shown previously that there exists an infinite family of temporal graphs for which any exploration schedule has arrival time Omega(n^2), making these bounds tight for general TEXP instances. We consider restricted instances of TEXP, in which the temporal graph given as input is, in every time step, of maximum degree d; we show an O(n^2/log n) bound on the arrival time when d is constant, and an O(d log d * n^2/log n) bound when d is given as some function of n.
Cite as

Thomas Erlebach and Jakob T. Spooner. Faster Exploration of Degree-Bounded Temporal Graphs. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 36:1-36:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{erlebach_et_al:LIPIcs.MFCS.2018.36,
  author =	{Erlebach, Thomas and Spooner, Jakob T.},
  title =	{{Faster Exploration of Degree-Bounded Temporal Graphs}},
  booktitle =	{43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018)},
  pages =	{36:1--36:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-086-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{117},
  editor =	{Potapov, Igor and Spirakis, Paul and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2018.36},
  URN =		{urn:nbn:de:0030-drops-96181},
  doi =		{10.4230/LIPIcs.MFCS.2018.36},
  annote =	{Keywords: temporal graph exploration, algorithmic graph theory, NP-complete problem}
}
  • Refine by Type
  • 8 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 5 2025
  • 1 2022
  • 1 2019
  • 1 2018

  • Refine by Author
  • 3 Erlebach, Thomas
  • 3 Spooner, Jakob T.
  • 1 Adamson, Duncan
  • 1 Ayoubi, Kamran
  • 1 Döring, Michelle
  • Show More...

  • Refine by Series/Journal
  • 8 LIPIcs

  • Refine by Classification
  • 3 Mathematics of computing → Graph algorithms
  • 2 Theory of computation → Graph algorithms analysis
  • 1 Mathematics of computing → Discrete mathematics
  • 1 Mathematics of computing → Graph theory
  • 1 Mathematics of computing → Paths and connectivity problems
  • Show More...

  • Refine by Keyword
  • 2 Temporal graphs
  • 1 Algorithmic Graph Theory
  • 1 Anonymous graphs
  • 1 Deterministic algorithm
  • 1 Dynamic graphs
  • Show More...

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