24 Search Results for "Renken, Malte"

Document
DOI: 10.4230/LIPIcs.STACS.2026.10
A Polynomial Bound on the Pathwidth of Graphs Edge-Coverable by k Shortest Paths

Authors: Julien Baste, Lucas De Meyer, Ugo Giocanti, Etienne Objois, and Timothé Picavet

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
Dumas, Foucaud, Perez and Todinca [SIAM J. Disc. Math., 2024] recently proved that every graph whose edge set can be covered by k shortest paths has pathwidth at most 3^k. In this paper, we improve this upper bound on the pathwidth to a polynomial bound; namely, we show that every graph whose edge set can be covered by k shortest paths has pathwidth O(k⁴), answering a question from the same paper. Moreover, we also prove that when k ≤ 3, every such graph has pathwidth at most k (and this bound is tight). Eventually, we show that even though there exist graphs with arbitrary large treewidth whose vertex set can be covered by 2 isometric trees, every graph whose set of edges can be covered by 2 isometric trees has treewidth at most 2.
Cite as

Julien Baste, Lucas De Meyer, Ugo Giocanti, Etienne Objois, and Timothé Picavet. A Polynomial Bound on the Pathwidth of Graphs Edge-Coverable by k Shortest Paths. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{baste_et_al:LIPIcs.STACS.2026.10,
  author =	{Baste, Julien and De Meyer, Lucas and Giocanti, Ugo and Objois, Etienne and Picavet, Timoth\'{e}},
  title =	{{A Polynomial Bound on the Pathwidth of Graphs Edge-Coverable by k Shortest Paths}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.10},
  URN =		{urn:nbn:de:0030-drops-254999},
  doi =		{10.4230/LIPIcs.STACS.2026.10},
  annote =	{Keywords: Structural Graph Theory, Coverings, Metrics, Pathwidth, Treewdidth, Parameterized Algorithms, Layerings}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.39
Efficient Algorithms for the Disjoint Shortest Paths Problem and Its Extensions

Authors: Keerti Choudhary, Amit Kumar, and Lakshay Saggi

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We study the 2-Disjoint Shortest Paths (2-DSP) problem: given a directed weighted graph and two terminal pairs (s₁,t₁) and (s₂,t₂), decide whether there exist vertex-disjoint shortest paths between each pair. Building on recent advances in disjoint shortest paths for DAGs and undirected graphs (Akmal et al. 2024), we present an O(mn log n)-time algorithm for this problem in weighted directed graphs that do not contain negative or zero weight cycles. This algorithm presents a significant improvement over the previously known O(m⁵n)-time bound (Berczi et al. 2017). Our approach exploits the algebraic structure of polynomials that enumerate shortest paths between terminal pairs. A key insight is that these polynomials admit a recursive decomposition, enabling efficient evaluation via dynamic programming over fields of characteristic two. Furthermore, we demonstrate how to report the corresponding paths in O(mn² log n)-time. In addition, we extend our techniques to a more general setting: given two terminal pairs (s₁, t₁) and (s₂, t₂) in a directed graph, find the minimum possible number of vertex intersections between any shortest path from s₁ to t₁ and s₂ to t₂. We call this the Minimum 2-Disjoint Shortest Paths (Min-2-DSP) problem. We provide in this paper the first efficient algorithm for this problem, including an O(m² n³)-time algorithm for directed graphs with positive edge weights, and an O(m+n)-time algorithm for DAGs and undirected graphs. Moreover, if the number of intersecting vertices is at least one, we show that it is possible to report the paths in the same O(m+n)-time. This is somewhat surprising, as there is no known o(mn) time algorithm for explicitly reporting the paths if they are vertex-disjoint, and is left as an open problem in (Akmal et al. 2024).
Cite as

Keerti Choudhary, Amit Kumar, and Lakshay Saggi. Efficient Algorithms for the Disjoint Shortest Paths Problem and Its Extensions. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 39:1-39:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{choudhary_et_al:LIPIcs.ITCS.2026.39,
  author =	{Choudhary, Keerti and Kumar, Amit and Saggi, Lakshay},
  title =	{{Efficient Algorithms for the Disjoint Shortest Paths Problem and Its Extensions}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{39:1--39:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.39},
  URN =		{urn:nbn:de:0030-drops-253267},
  doi =		{10.4230/LIPIcs.ITCS.2026.39},
  annote =	{Keywords: Disjoint paths, Disjoint shortest paths, Algebraic graph algorithms}
}
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.ESA.2025.67
Compact Representation of Semilinear and Terrain-Like Graphs

Authors: Jean Cardinal and Yelena Yuditsky

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We consider the existence and construction of biclique covers of graphs, consisting of coverings of their edge sets by complete bipartite graphs. The size of such a cover is the sum of the sizes of the bicliques. Small-size biclique covers of graphs are ubiquitous in computational geometry, and have been shown to be useful compact representations of graphs. We give a brief survey of classical and recent results on biclique covers and their applications, and give new families of graphs having biclique covers of near-linear size. In particular, we show that semilinear graphs, whose edges are defined by linear relations in bounded dimensional space, always have biclique covers of size O(npolylog n). This generalizes many previously known results on special classes of graphs including interval graphs, permutation graphs, and graphs of bounded boxicity, but also new classes such as intersection graphs of L-shapes in the plane. It also directly implies the bounds for Zarankiewicz’s problem derived by Basit, Chernikov, Starchenko, Tao, and Tran (Forum Math. Sigma, 2021). We also consider capped graphs, also known as terrain-like graphs, defined as ordered graphs forbidding a certain ordered pattern on four vertices. Terrain-like graphs contain the induced subgraphs of terrain visibility graphs. We give an elementary proof that these graphs admit biclique partitions of size O(nlog³ n). This provides a simple combinatorial analogue of a classical result from Agarwal, Alon, Aronov, and Suri on polygon visibility graphs (Discrete Comput. Geom. 1994). Finally, we prove that there exists families of unit disk graphs on n vertices that do not admit biclique coverings of size o(n^{4/3}), showing that we are unlikely to improve on Szemerédi-Trotter type incidence bounds for higher-degree semialgebraic graphs.
Cite as

Jean Cardinal and Yelena Yuditsky. Compact Representation of Semilinear and Terrain-Like Graphs. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 67:1-67:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cardinal_et_al:LIPIcs.ESA.2025.67,
  author =	{Cardinal, Jean and Yuditsky, Yelena},
  title =	{{Compact Representation of Semilinear and Terrain-Like Graphs}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{67:1--67:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2025.67},
  URN =		{urn:nbn:de:0030-drops-245359},
  doi =		{10.4230/LIPIcs.ESA.2025.67},
  annote =	{Keywords: Biclique covers, intersection graphs, visibility graphs, Zarankiewicz’s problem}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.23
Novel Complexity Results for Temporal Separators with Deadlines

Authors: Riccardo Dondi and Manuel Lafond

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
We consider two variants, (s,z,𝓁)-Temporal Separator and (s,z,𝓁)-Temporal Cut, respectively, of the vertex separator and the edge cut problem in temporal graphs. The goal is to remove the minimum number of vertices (temporal edges, respectively) in order to delete all the temporal paths that have time travel at most 𝓁 between a source vertex s and target vertex z. First, we solve an open problem in the literature showing that (s,z,𝓁)-Temporal Separator is NP-hard even when the underlying graph has pathwidth bounded by four. We complement this result showing that (s,z,𝓁)-Temporal Separator can be solved in polynomial time for graphs of pathwidth bounded by three. Then we consider the approximability of (s,z,𝓁)-Temporal Separator and we show that it cannot be approximated within factor 2^Ω(log^{1-ε}|V|) for any constant ε > 0, unless NP ⊆ ZPP (V is the vertex set of the input temporal graph) and that the strict version is approximable within factor 𝓁-1 (we show also that it is unliklely that this factor can be improved). Then we consider the (s,z,𝓁)-Temporal Cut problem, we show that it is APX-hard and we present a 2 log₂(2𝓁) approximation algorithm.
Cite as

Riccardo Dondi and Manuel Lafond. Novel Complexity Results for Temporal Separators with Deadlines. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dondi_et_al:LIPIcs.WADS.2025.23,
  author =	{Dondi, Riccardo and Lafond, Manuel},
  title =	{{Novel Complexity Results for Temporal Separators with Deadlines}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.23},
  URN =		{urn:nbn:de:0030-drops-242545},
  doi =		{10.4230/LIPIcs.WADS.2025.23},
  annote =	{Keywords: Temporal Graphs, Graph Algorithms, Graph Separators, Parameterized Complexity, Approximation Complexity}
}
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
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.120
Treewidth Parameterized by Feedback Vertex Number

Authors: Hendrik Molter, Meirav Zehavi, and Amit Zivan

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We provide the first algorithm for computing an optimal tree decomposition for a given graph G that runs in single exponential time in the feedback vertex number of G, that is, in time 2^{𝒪(fvn(G))}⋅ n^{𝒪(1)}, where fvn(G) is the feedback vertex number of G and n is the number of vertices of G. On a classification level, this improves the previously known results by Chapelle et al. [Discrete Applied Mathematics '17] and Fomin et al. [Algorithmica '18], who independently showed that an optimal tree decomposition can be computed in single exponential time in the vertex cover number of G. One of the biggest open problems in the area of parameterized complexity is whether we can compute an optimal tree decomposition in single exponential time in the treewidth of the input graph. The currently best known algorithm by Korhonen and Lokshtanov [STOC '23] runs in 2^{𝒪(tw(G)²)}⋅ n⁴ time, where tw(G) is the treewidth of G. Our algorithm improves upon this result on graphs G where fvn(G) ∈ o(tw(G)²). On a different note, since fvn(G) is an upper bound on tw(G), our algorithm can also be seen either as an important step towards a positive resolution of the above-mentioned open problem, or, if its answer is negative, then a mark of the tractability border of single exponential time algorithms for the computation of treewidth.
Cite as

Hendrik Molter, Meirav Zehavi, and Amit Zivan. Treewidth Parameterized by Feedback Vertex Number. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 120:1-120:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{molter_et_al:LIPIcs.ICALP.2025.120,
  author =	{Molter, Hendrik and Zehavi, Meirav and Zivan, Amit},
  title =	{{Treewidth Parameterized by Feedback Vertex Number}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{120:1--120:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.120},
  URN =		{urn:nbn:de:0030-drops-234979},
  doi =		{10.4230/LIPIcs.ICALP.2025.120},
  annote =	{Keywords: Treewidth, Tree Decomposition, Exact Algorithms, Single Exponential Time, Feedback Vertex Number, Dynamic Programming}
}
Document
DOI: 10.4230/LIPIcs.SAND.2025.9
Spanner Enumeration for Temporal Graphs

Authors: Kazuhiro Kurita, Andrea Marino, Jason Schoeters, and Takeaki Uno

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

Abstract
A spanner of a temporal graph is a subset of edges that preserves connectivity over time between vertices. A minimal spanner is one in which no additional edges can be removed without breaking this connectivity. Our focus is on enumerating minimal spanners for a given temporal graph. We explore several variations of this problem based on the type of connectivity that must be maintained, ranging from one-to-all connectivity to one-to-all-to-one, many-to-all, and finally all-to-all connectivity. We establish that these problems become progressively harder: (i) We present a polynomial-delay enumeration algorithm for one-to-all connectivity; (ii) We prove Dual-hardness for both one-to-all-to-one and many-to-all connectivity, even in the restricted case of two-to-all; (iii) Finally, for all-to-all connectivity, we show that enumeration cannot be performed in output-polynomial time unless P = NP.
Cite as

Kazuhiro Kurita, Andrea Marino, Jason Schoeters, and Takeaki Uno. Spanner Enumeration for Temporal Graphs. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kurita_et_al:LIPIcs.SAND.2025.9,
  author =	{Kurita, Kazuhiro and Marino, Andrea and Schoeters, Jason and Uno, Takeaki},
  title =	{{Spanner Enumeration for Temporal Graphs}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{9:1--9:21},
  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.9},
  URN =		{urn:nbn:de:0030-drops-230621},
  doi =		{10.4230/LIPIcs.SAND.2025.9},
  annote =	{Keywords: temporal graphs, temporal spanners, one-to-all connectivity, all-to-all connectivity enumeration, NP-completeness, Dual-hardness, binary partition tree, flashlight search, polynomial delay}
}
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
DOI: 10.4230/LIPIcs.SAND.2025.7
Better Late, Then? The Hardness of Choosing Delays to Meet Passenger Demands in Temporal Graphs

Authors: David C. Kutner and Anouk Sommer

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

Abstract
In train networks, carefully-chosen delays may be beneficial for certain passengers, who would otherwise miss some connection. Given a simple (directed or undirected) temporal graph and a set of passengers (each specifying a starting vertex, an ending vertex, and a desired arrival time), we ask whether it is possible to delay some of the edges of the temporal graph to realize all the passengers' demands. We call this problem DelayBetter (DB), and study it along with two variants: in δ-DelayBetter, each delay must be of at most δ; in (δ-)Path DB, passengers also fully specify the vertices they should visit on their journey. On the positive side, we give a polynomial-time algorithm for Path DB and δ-Path DB, and obtain as a corollary a polynomial-time algorithm for DB and δ-DB on trees. We also provide an fpt algorithm for both problems parameterized by the size of the graph’s Feedback Edge Set together with the number of passengers. On the negative side, we show NP-completeness of (1-)DB on bounded-degree temporal graphs even when the lifetime is 2, and of (10-)DB on bounded-degree planar temporal graphs of lifetime 19. Our results complement previous work studying reachability problems in temporal graphs with delaying operations. This is to our knowledge the first such problem in which the aim is to facilitate travel between specific points (as opposed to facilitating or impeding a broadcast from one or many sources).
Cite as

David C. Kutner and Anouk Sommer. Better Late, Then? The Hardness of Choosing Delays to Meet Passenger Demands in Temporal Graphs. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kutner_et_al:LIPIcs.SAND.2025.7,
  author =	{Kutner, David C. and Sommer, Anouk},
  title =	{{Better Late, Then? The Hardness of Choosing Delays to Meet Passenger Demands in Temporal Graphs}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{7:1--7:18},
  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.7},
  URN =		{urn:nbn:de:0030-drops-230604},
  doi =		{10.4230/LIPIcs.SAND.2025.7},
  annote =	{Keywords: Temporal Graphs, Computational Complexity, Delay Management, Train Networks}
}
Document
DOI: 10.4230/LIPIcs.SAND.2025.6
Dismountability in Temporal Cliques Revisited

Authors: Daniele Carnevale, Arnaud Casteigts, and Timothée Corsini

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

Abstract
A temporal graph is a graph whose edges are available only at certain points in time. It is temporally connected if the nodes can reach each other by paths that traverse the edges chronologically (temporal paths). Unlike static graphs, temporal graphs do not always admit small subsets of edges that preserve connectivity (temporal spanners) - there exist temporal graphs with Θ(n²) edges, all of which are critical. In the case of temporal cliques (the underlying graph is complete), spanners of size O(nlog n) are guaranteed. The original proof of this result by Casteigts et al. [ICALP 2019] combines a number of techniques, one of which is called dismountability. In a recent work, Angrick et al. [ESA 2024] simplified the proof and showed, among other things, that a one-sided version of dismountability can replace elegantly the second part of the proof. In this paper, we revisit methodically the dismountability principle. We start by characterizing the structure that a temporal clique must have if it is non 1-hop dismountable, then neither 1-hop nor 2-hop (i.e. non {1,2}-hop) dismountable, and finally non {1,2,3}-hop dismountable. It turns out that if a clique is k-hop dismountable for any other k, then it must also be {1,2,3}-hop dismountable, thus no additional structure can be obtained beyond this point. Interestingly, excluding 1-hop and 2-hop dismountability is already sufficient for reducing the spanner problem from cliques to extremally matched bicliques, where the O(nlog n) result is subsequently obtained. Put together with the strategy of Angrick et al., this entire result can now be recovered using only dismountability. An interesting by-product of our analysis is that any minimal counter-example to the existence of 4n spanners must satisfy the properties of non {1,2,3}-hop dismountable cliques. In the second part, we discuss further connections between dismountability and another technique called pivotability. In particular, we show that if a temporal clique is recursively k-hop dismountable, then it is also pivotable (and thus admits a 2n spanner, whatever k). We also study a family of labelings called full-range that forces both dismountability and pivotability. The latter gives some evidence that large lifetimes could be exploited more generally for the construction of spanners.
Cite as

Daniele Carnevale, Arnaud Casteigts, and Timothée Corsini. Dismountability in Temporal Cliques Revisited. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{carnevale_et_al:LIPIcs.SAND.2025.6,
  author =	{Carnevale, Daniele and Casteigts, Arnaud and Corsini, Timoth\'{e}e},
  title =	{{Dismountability in Temporal Cliques Revisited}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{6:1--6:18},
  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.6},
  URN =		{urn:nbn:de:0030-drops-230591},
  doi =		{10.4230/LIPIcs.SAND.2025.6},
  annote =	{Keywords: Dynamic networks, Temporal graphs, Reachability, Dismountability, Pivotability, Temporal spanners, Full-range graphs}
}
Document
DOI: 10.4230/LIPIcs.SAND.2025.3
Temporal Connectivity Augmentation

Authors: Thomas Bellitto, Jules Bouton Popper, and Bruno Escoffier

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

Abstract
Connectivity in temporal graphs relies on the notion of temporal paths, in which edges follow a chronological order (either strict or non-strict). In this work, we investigate the question of how to make a temporal graph connected. More precisely, we tackle the problem of finding, among a set of proposed temporal edges, the smallest subset such that its addition makes the graph temporally connected (TCA). We study the complexity of this problem and variants, under restricted lifespan of the graph, i.e. the maximum time step in the graph. Our main result on TCA is that for any fixed lifespan at least 2, it is NP-complete in both the strict and non-strict setting. We additionally provide a set of restrictions in the non-strict setting which makes the problem solvable in polynomial time and design an algorithm achieving this complexity. Interestingly, we prove that the source variant (making a given vertex a source in the augmented graph) is as difficult as TCA. On the opposite, we prove that the version where a list of connectivity demands has to be satisfied is solvable in polynomial time, when the size of the list is fixed. Finally, we highlight a variant of the previous case for which even with two pairs the problem is already NP-hard.
Cite as

Thomas Bellitto, Jules Bouton Popper, and Bruno Escoffier. Temporal Connectivity Augmentation. In 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 330, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bellitto_et_al:LIPIcs.SAND.2025.3,
  author =	{Bellitto, Thomas and Popper, Jules Bouton and Escoffier, Bruno},
  title =	{{Temporal Connectivity Augmentation}},
  booktitle =	{4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2025)},
  pages =	{3:1--3:16},
  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.3},
  URN =		{urn:nbn:de:0030-drops-230565},
  doi =		{10.4230/LIPIcs.SAND.2025.3},
  annote =	{Keywords: Temporal graph, temporal connectivity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.17
Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths

Authors: Matthias Bentert, Fedor V. Fomin, and Petr A. Golovach

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
We examine the possibility of approximating Maximum Vertex-Disjoint Shortest Paths. In this problem, the input is an edge-weighted (directed or undirected) n-vertex graph G along with k terminal pairs (s_1,t_1),(s_2,t_2),…,(s_k,t_k). The task is to connect as many terminal pairs as possible by pairwise vertex-disjoint paths such that each path is a shortest path between the respective terminals. Our work is anchored in the recent breakthrough by Lochet [SODA '21], which demonstrates the polynomial-time solvability of the problem for a fixed value of k. Lochet’s result implies the existence of a polynomial-time ck-approximation for Maximum Vertex-Disjoint Shortest Paths, where c ≤ 1 is a constant. (One can guess 1/c terminal pairs to connect in k^O(1/c) time and then utilize Lochet’s algorithm to compute the solution in n^f(1/c) time.) Our first result suggests that this approximation algorithm is, in a sense, the best we can hope for. More precisely, assuming the gap-ETH, we exclude the existence of an o(k)-approximation within f(k) ⋅ poly(n) time for any function f that only depends on k. Our second result demonstrates the infeasibility of achieving an approximation ratio of m^{1/2-ε} in polynomial time, unless P = NP. It is not difficult to show that a greedy algorithm selecting a path with the minimum number of arcs results in a ⌈√𝓁⌉-approximation, where 𝓁 is the number of edges in all the paths of an optimal solution. Since 𝓁 ≤ n, this underscores the tightness of the m^{1/2-ε}-inapproximability bound. Additionally, we establish that Maximum Vertex-Disjoint Shortest Paths is fixed-parameter tractable when parameterized by 𝓁 but does not admit a polynomial kernel. Our hardness results hold for undirected graphs with unit weights, while our positive results extend to scenarios where the input graph is directed and features arbitrary (non-negative) edge weights.
Cite as

Matthias Bentert, Fedor V. Fomin, and Petr A. Golovach. Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bentert_et_al:LIPIcs.STACS.2025.17,
  author =	{Bentert, Matthias and Fomin, Fedor V. and Golovach, Petr A.},
  title =	{{Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{17:1--17:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.17},
  URN =		{urn:nbn:de:0030-drops-228422},
  doi =		{10.4230/LIPIcs.STACS.2025.17},
  annote =	{Keywords: Inapproximability, Fixed-parameter tractability, Parameterized approximation}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.29
On Reliability of the Extrema Propagation Technique in Random Environment

Authors: Jacek Cichoń, Dawid Dworzański, and Karol Gotfryd

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)

Abstract
We study the reliability of the following simple mechanism for spreading information in a communication network in the presence of random message loss. Initially, some nodes have information that they want to distribute throughout the network. Each node that has received the information tries to broadcast it to all its neighbors. However, due to interference or communication failures, each transmission between two nodes is broken independently with some fixed probability. This transmission mechanism is the basis for the extrema propagation technique, proposed and analyzed in [Carlos Baquero et al., 2012; Baquero et al., 2009; Jacek Cicho{ń} et al., 2012]. Extrema propagation is a simple but powerful method of spreading the extreme values stored by the nodes. In a fully reliable environment, only the number of rounds equal to the network diameter is required for all nodes to be informed. It was shown empirically in [Carlos Baquero et al., 2012] that it also performs well in the presence of link failures and message loss. Extrema propagation is an algorithmic framework that was adopted for designing efficient method for distributed data aggregation, such as estimation of cardinalities, sums, and averages, estimation of data distribution via histograms and random sampling (cf. [Baquero et al., 2009; Karol Gotfryd and Jacek Cichoń, 2023]). In this paper, we propose a formal network model in which random transmission failures occur and analyze the operation time of the extrema propagation technique for any connected network graph. We provide new general probabilistic upper bounds on the number of rounds needed to spread the extreme values that depend only on the number of nodes, the diameter of the network, and the probability of successful transmission. For some special families of graphs, we also derive specific, more accurate estimates. Our theoretical and experimental results confirm the reliability and efficiency of the extrema propagation technique in faulty or noisy environments.
Cite as

Jacek Cichoń, Dawid Dworzański, and Karol Gotfryd. On Reliability of the Extrema Propagation Technique in Random Environment. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cichon_et_al:LIPIcs.OPODIS.2024.29,
  author =	{Cicho\'{n}, Jacek and Dworza\'{n}ski, Dawid and Gotfryd, Karol},
  title =	{{On Reliability of the Extrema Propagation Technique in Random Environment}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{29:1--29:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.29},
  URN =		{urn:nbn:de:0030-drops-225657},
  doi =		{10.4230/LIPIcs.OPODIS.2024.29},
  annote =	{Keywords: wireless ad-hoc networks, extrema propagation, distributed data aggregation, fault tolerant aggregation, randomly evolving networks}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.9
Detecting Disjoint Shortest Paths in Linear Time and More

Authors: Shyan Akmal, Virginia Vassilevska Williams, and Nicole Wein

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
In the k-Disjoint Shortest Paths (k-DSP) problem, we are given a graph G (with positive edge weights) on n nodes and m edges with specified source vertices s_1, … , s_k, and target vertices t_1, … , t_k, and are tasked with determining if G contains vertex-disjoint (s_i,t_i)-shortest paths. For any constant k, it is known that k-DSP can be solved in polynomial time over undirected graphs and directed acyclic graphs (DAGs). However, the exact time complexity of k-DSP remains mysterious, with large gaps between the fastest known algorithms and best conditional lower bounds. In this paper, we obtain faster algorithms for important cases of k-DSP, and present better conditional lower bounds for k-DSP and its variants. Previous work solved 2-DSP over weighted undirected graphs in O(n⁷) time, and weighted DAGs in O(mn) time. For the main result of this paper, we present optimal linear time algorithms for solving 2-DSP on weighted undirected graphs and DAGs. Our linear time algorithms are algebraic however, and so only solve the detection rather than search version of 2-DSP (we show how to solve the search version in O(mn) time, which is faster than the previous best runtime in weighted undirected graphs, but only matches the previous best runtime for DAGs). We also obtain a faster algorithm for k-Edge Disjoint Shortest Paths (k-EDSP) in DAGs, the variant of k-DSP where one seeks edge-disjoint instead of vertex-disjoint paths between sources and their corresponding targets. Algorithms for k-EDSP on DAGs from previous work take Ω(m^k) time. We show that k-EDSP can be solved over DAGs in O(mn^{k-1}) time, matching the fastest known runtime for solving k-DSP over DAGs. Previous work established conditional lower bounds for solving k-DSP and its variants via reductions from detecting cliques in graphs. Prior work implied that k-Clique can be reduced to 2k-DSP in DAGs and undirected graphs with O((kn)²) nodes. We improve this reduction, by showing how to reduce from k-Clique to k-DSP in DAGs and undirected graphs with O((kn)²) nodes (halving the number of paths needed in the reduced instance). A variant of k-DSP is the k-Disjoint Paths (k-DP) problem, where the solution paths no longer need to be shortest paths. Previous work reduced from k-Clique to p-DP in DAGs with O(kn) nodes, for p = k + k(k-1)/2. We improve this by showing a reduction from k-Clique to p-DP, for p = k + ⌊k²/4⌋. Under the k-Clique Hypothesis from fine-grained complexity, our results establish better conditional lower bounds for k-DSP for all k ≥ 4, and better conditional lower bounds for p-DP for all p ≤ 4031. Notably, our work gives the first nontrivial conditional lower bounds 4-DP in DAGs and 4-DSP in undirected graphs and DAGs. Before our work, nontrivial conditional lower bounds were only known for k-DP and k-DSP on such graphs when k ≥ 6.
Cite as

Shyan Akmal, Virginia Vassilevska Williams, and Nicole Wein. Detecting Disjoint Shortest Paths in Linear Time and More. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 9:1-9:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{akmal_et_al:LIPIcs.ICALP.2024.9,
  author =	{Akmal, Shyan and Vassilevska Williams, Virginia and Wein, Nicole},
  title =	{{Detecting Disjoint Shortest Paths in Linear Time and More}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{9:1--9:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.9},
  URN =		{urn:nbn:de:0030-drops-201529},
  doi =		{10.4230/LIPIcs.ICALP.2024.9},
  annote =	{Keywords: disjoint shortest paths, algebraic graph algorithms, disjoint paths, fine-grained complexity, clique}
}
  • Refine by Type
  • 24 Document/PDF
  • 14 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 12 2025
  • 1 2024
  • 2 2023
  • 3 2022
  • Show More...

  • Refine by Author
  • 9 Renken, Malte
  • 6 Molter, Hendrik
  • 4 Zschoche, Philipp
  • 3 Niedermeier, Rolf
  • 2 Bentert, Matthias
  • Show More...

  • Refine by Series/Journal
  • 24 LIPIcs

  • Refine by Classification
  • 8 Theory of computation → Graph algorithms analysis
  • 5 Mathematics of computing → Discrete mathematics
  • 5 Mathematics of computing → Graph algorithms
  • 5 Theory of computation → Parameterized complexity and exact algorithms
  • 4 Mathematics of computing → Paths and connectivity problems
  • Show More...

  • Refine by Keyword
  • 3 Parameterized Algorithms
  • 3 Temporal Graphs
  • 3 Temporal graph
  • 3 Temporal graphs
  • 3 temporal connectivity
  • 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