Simple, Strict, Proper, and Directed: Comparing Reachability in Directed and Undirected Temporal Graphs

Michelle D\"oring

REVIEW 4 major objections 5 minor 21 references

Simple, Strict, Proper, and Directed: Comparing Reachability in Directed and Undirected Temporal Graphs

T0 review · 4 major / 5 minor · reviewed 2026-08-10 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read For directed temporal graphs, every reachability pattern expressible in any natural setting is reproduced by a strict, single-labeled graph, so the directed hierarchy is one chain.

desk verdict Real contribution to temporal graph hierarchies, but the directed single-strand result rests on an unproved global-disjointness step in Lemma 4.5. read the letter →

arxiv 2501.11697 v1 pith:VOLN3557 submitted 2025-01-20 cs.DM cs.DC

Michelle Döring This is my paper · ORCID

classification cs.DMcs.DC MSC 68R1005C20

keywords temporalgraphsdirectedreachabilityequivalencestrictvsnon-strictpathsproperarbitrarysimplemulti-labelededgesdynamicnetworks

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper sets out to order the natural settings of temporal graphs—whether time labels must strictly increase, whether adjacent edges may share a time, and whether an edge may carry several times—into a hierarchy by what reachability relations they can express, now adding the directed/undirected axis. The main claim is that for directed temporal graphs the hierarchy is a single chain: the strict & simple setting (every edge appears once, and paths must use strictly increasing times) can reproduce the reachability graph of every directed temporal graph, while no non-strict or proper class can reproduce everything the strict class can. For undirected graphs the paper closes the last open separation: non-strict & simple undirected graphs cannot be transformed into strict & simple ones without changing reachability, so the undirected hierarchy splits into two incomparable strands rather than one. The point of the hierarchy is transfer: a positive result in a more expressive class carries down to weaker classes, and a hardness result in a weaker class carries up.

What carries the argument

The machinery has three parts. The first is the reachability graph R(G), the static directed graph of who can reach whom, used as the invariant under comparison. The second is the saturation observation: replacing G by R(G) with uniform label 1 shows directed & strict & simple is universal for directed reachability. The third is a pair of structural lemmas: Lemma 4.1 says any directed cycle in a non-strict temporal graph creates at least one transitive reachability, so a 3-cycle with all labels 1 separates strict from non-strict; Lemma 4.2 says a proper directed graph on n > 2 vertices whose reachability graph is a clique must contain at least n + 1 temporal edges, and this count separates non-strict & simple from proper & simple. Two transformations carry the positive direction: support-dilation, which orders strongly connected components within each snapshot and dilates their interior to make the graph proper while preserving path supports, and reachability-dilation, which replaces each strongly connected component by a bidirected spanning tree with distinct increasing labels, preserving reachability with only a doubling of the lifetime. A directed semaphore gadget, which subdivides edges through auxiliary vertices and tilts labels by an edge-coloring, shows all directed settings are equivalent under induced-reachability.

What would settle it

Exhibit a directed proper temporal graph on three vertices with exactly three temporal edges whose reachability graph is the complete directed graph; Lemma 4.2 says this cannot exist, and its existence would collapse the proof of Lemma 4.5, which separates non-strict & simple from proper & simple by counting six possible temporal edges against the eight needed for two three-vertex cliques.

Watch

Extended reading notes

Core claim

The paper's central discovery is that directedness changes the shape of the reachability hierarchy. The central move is Observation 4.13: given any directed temporal graph G, build a static directed graph on the same vertices with an edge (u,v) whenever u can reach v in G, and give every edge time label 1. In the strict & simple setting the only temporal paths of length one use the single label, and longer strict paths are impossible because 1 is not strictly greater than 1; hence the reachability graph is unchanged. Consequently directed & strict & simple, and therefore directed & strict, is the most expressive directed class. The paper then proves the matching negative results: a directed triangle with three label-1 edges has a reachability graph no non-strict directed graph can realize, because Lemma 4.1 forces an extra transitive reachability inside any cycle, and a four-vertex gadget built from two three-cliques at distinct times cannot be realized in directed & proper & simple, because Lemma 4.2 says a three-vertex clique in a proper graph needs four temporal edges while the simple setting permits only six edges between the three center vertices to cover two time steps. These results, together with support-dilation and reachability-dilation transformations, fix the full directed ordering and answer the two open undirected comparisons.

Load-bearing premise

The load-bearing premise is that a directed temporal graph in which no two touching edges share a time needs more temporal edges than vertices before every vertex can reach every other; the paper asserts this without a full derivation, and the separation between the single-label non-strict class and the single-label proper class depends directly on that count.

Editorial extensions

If this is right

For problems that depend only on the reachability graph, studying directed & strict & simple graphs loses nothing, and algorithms or positive results there apply to every directed setting.
The two undirected strands are incomparable: reachability results cannot be transferred between the strict & simple and non-strict & simple undirected classes, although within each strand the usual transfer rules hold.
Every undirected temporal graph has a directed counterpart with the same reachability graph, but no directed temporal graph can be rewritten as an undirected one, so directed settings are strictly more expressive than undirected ones.
Strict classes dominate non-strict classes in both the directed and undirected hierarchies, so any reachability graph realizable by a non-strict class is also realizable by a strict class, with the reverse failing.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the directed single-chain result is taken at face value, the realizability question for directed temporal graphs becomes nearly trivial: because every finite directed graph is its own reachability graph under the uniform-label-1 construction, the set of reachability graphs of any directed setting is exactly the set of all finite directed graphs.
The 8-versus-6 counting in the separation of non-strict & simple from proper & simple suggests a testable invariant: the minimal number of temporal edges needed to realize a clique at two distinct times in a simple proper graph, and checking whether any other three-vertex gadget could do it with fewer edges would probe the robustness of that separation.
A positive answer to the paper's remaining open question, whether undirected & non-strict graphs can be mapped to directed & proper & simple while preserving reachability, would mean that an undirected edge never needs more than one label per direction, unifying the non-strict undirected strand with the directed chain.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Quick take: this is a genuine extension of the CCS framework and a useful result for the temporal-graph subfield, but the central directed hierarchy has a load-bearing proof gap. The new material is the directed single-strand hierarchy—Observation 4.13, that every directed temporal graph is reachability-equivalent to a directed & strict & simple graph, is the clean top of that hierarchy—plus the resolution of CCS's undirected open question and the merged directed/undirected comparison. Observation 4.13 is almost too simple to be novel, but it is exactly the observation that makes the directed side organize into one strand.

What is done well: the paper is explicit about what comes from CCS and what is new. Support-dilation and reachability-dilation are sensible generalizations, and the directed semaphore adapts cleanly. Theorem 3.1's proof strategy—forcing the footprint by forbidding shortcuts and then arguing no simple strict labeling works—looks sound. The paper fits no parameters and does not argue circularly; its reliance on CCS is legitimate background. The writing is mostly readable and the figures are genuinely helpful.

The soft spots are concentrated in Section 4. The load-bearing separation Lemma 4.5 is not fully proved. The final 8-vs-6 edge count assumes that the a-phase and c-phase each require a temporally disjoint x,y,z-clique. What is actually established is only per-source ordering: at each center i, λ(a_i,i) < λ(i,b) < λ(c,i) < λ(i,d). That does not imply that all a-phase traffic finishes before all c-phase traffic starts, and nothing rules out a single six-edge labeling serving both phases. This is the step on which the entire single-strand directed hierarchy depends, so it needs a real argument or independent verification. The stress-test note is right about this. I would not put the main weight on Lemma 4.2: its proof is one sentence, but the n+1 bound is correct; that is a presentation issue, not a correctness issue. Support-dilation's ordering and label-shifting details are also underspecified, and Theorem 4.15 is deferred to [7] rather than proved. The missing citation placeholder in the future-work section is minor.

This deserves a serious referee. The right outcome is likely major revision directed at Lemma 4.5 and the support-dilation details, not a desk reject. If Lemma 4.5 gets fixed or verified, the paper is a solid contribution.

Referee Report

4 major / 5 minor

Summary. The paper extends the framework of Casteigts, Corsini, and Sarkar for comparing temporal graph settings under bijective, support, reachability, and induced-reachability equivalence, adding the directed-vs-undirected dimension. The main claims are: (i) the directed reachability settings form a single-strand hierarchy in which directed & strict & simple is the most expressive class and directed & proper & simple the least, with strict classes strictly more expressive than non-strict classes; (ii) the undirected hierarchy has two incomparable strands, resolving two open questions from the prior work; and (iii) every undirected setting transforms into its directed counterpart under reachability equivalence, while no directed setting transforms into an undirected one. The paper introduces several transformations, including support-dilation and reachability-dilation, and uses a series of separating structures to establish strictness of the hierarchy.

Significance. If the results are correct, the paper provides a complete taxonomy of expressiveness for temporal graph settings under reachability equivalence, answering open questions from the CCS framework and clarifying the role of edge direction. The observation that any directed temporal graph can be transformed to a directed & strict & simple graph by taking its reachability graph as the footprint with a uniform label (Observation 4.13) is elegant and potentially very useful for transferring algorithmic results. The reachability-dilation construction with only linear label blow-up is also a valuable contribution. However, the central directed hierarchy rests critically on Lemma 4.5, whose proof is incomplete in a load-bearing way; until that gap is repaired, the main classification should be considered unproven.

major comments (4)

[Section 4.1, Lemma 4.5 (final paragraph)] The proof asserts that the a-phase and c-phase traversals of the center clique x,y,z must occur at two different points in time, and therefore require eight temporal edges among x,y,z, contradicting simplicity (at most six). The only supporting evidence is the per-source inequality λ(a_i,i) < λ(i,b_{f(i)}) < λ(i,c_{g(i)}) < λ(i,d_i), which orders labels of edges incident to each individual center vertex i. This inequality does not establish that all a-phase uses of the center-clique edges finish before any c-phase use begins. In particular, it does not preclude c_{g(i)} from reaching its entry center before the (unique) clique time and then using the same set of center-clique edges as the a-phase. Without a rigorous global-time-separation argument, the claimed 8-vs-6 contradiction collapses, and the separation D & non-strict & simple ̸⇝R D & proper & simple is not established. Since this separation is load-bearing for the single-strand directed hierarchy, the proof must be repaired or replaced.
[Section 4.1, Lemma 4.5 (final paragraph)] The notation in the key concluding paragraph is inconsistent and prevents verification. The text lists edges (a_i,i), (c_{g(i)},i), (i,b_{f(i)}), (i,d_i), but then writes an inequality involving λ(i,c_{g(i)}), which is the reverse of the edge (c_{g(i)},i), and also refers to c_{f(i)} where c_{g(i)} is presumably meant. The intended inequality must be stated precisely, and its derivation from the reachability requirements (a_i reaches b_{f(i)} and d_i, c_{g(i)} reaches every d_j but no b_j) must be spelled out step by step.
[Section 4, Lemma 4.2] The proof of Lemma 4.2 is a hand-wave: after reducing to the case of a directed cycle with n temporal edges, it states that 'it is impossible to label the edges in a way that forms strictly increasing temporal paths between all vertex pairs' without any argument. This lemma is used in Lemma 4.5 to conclude that a 3-vertex clique in a D & proper graph requires four temporal edges. Even if the n+1 lower bound is true, the proof as written is not sufficient for a formal paper; a rigorous argument (or a precise citation to a known theorem) is required.
[Section 5, Definition 5.2] The paper proposes an alternative definition of 'proper' for directed temporal graphs, forbidding equal labels only on edges of the form (u,v) and (v,x), and claims it is 'more convenient.' It is not shown to be equivalent, with respect to reachability, to the standard definition used throughout Sections 2–4, nor is it stated explicitly that all earlier directed results remain valid under the new definition. Since Observation 5.1 and Lemma 5.4 rely on this redefinition, the paper must either prove the equivalence of the two definitions in the relevant settings or use the standard definition consistently.

minor comments (5)

[Introduction] The name of the prior work is misspelled as 'Casteigt, Corsini, and Sakar'; it should be 'Casteigts, Corsini, and Sarkar.'
[Section 4.3.2] The section is titled 'Saturation' but it actually presents the trivial reachability-graph construction of Observation 4.13, which is different from the undirected saturation process described earlier. The title should be changed or the relation to saturation should be explained.
[Section 4.1, Lemma 4.5 (construction)] The labels in the figure and the edge sets E1–E4 should be checked for consistency; for instance, the text mentions labels 2.5 and 5.5 while the figure shows some values like 2.3 and 5.3, and it is not immediately clear which edges carry which labels.
[Section 4.1, Lemma 4.5, Claim 1] The phrase 'every direct edge (β,α) would form a directed triangle with the corresponding green edges (α,h_β^α), (h_β^α,β)' is confusing: if the direct edge is (β,α), the triangle would consist of (β,α), (α,h), (h,β), not the two green edges as listed. The sentence should be rephrased to identify the three edges of the forbidden triangle.
[Global] There are numerous typos and minor grammatical errors, including inconsistent ordering of 'simple & proper' versus 'proper & simple' (e.g., 'D & simple & proper' in Corollary 4.16 vs 'D & proper & simple' elsewhere), and phrases like 'the directed triangle still separates the strict setting from the proper and from the non-strict settings' that could be clearer. A thorough copyedit is recommended.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivations are definition-based, constructive, and do not reduce to their own inputs.

full rationale

I traced the paper's derivation chain. The central hierarchy claims for directed temporal graphs are established by constructive transformations (support-dilation, reachability-dilation, semaphore, and the all-labels-1 construction) and by explicit separating structures. Observation 4.13 is the only step that might superficially look self-referential, since H is defined from R(G); but the proof that R(H)=R(G) is direct: assigning label 1 to every edge of R(G) in the strict setting forbids all length-2 paths because the labels would have to strictly increase, so the reachability graph of H is exactly its footprint, i.e. R(G). This is a legitimate construction, not a fitted parameter renamed as a prediction. Lemma 4.5's 8-vs-6 temporal-edge count and the terse proof of Lemma 4.2 are potential rigor concerns about whether the claimed separation is fully proved, but they are not circular: no conclusion is assumed as an input, and no cited uniqueness theorem or prior result by the author forces the outcome. The only self-citation, reference [11], appears in a list of reachability applications and is not load-bearing. The paper's reliance on the external CCS framework [7] is independent published work, not a self-citation chain. Overall, the derivation is self-contained from the definitions, and no circular step is present.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted: the paper is a purely combinatorial classification. The central claims rely on the external CCS framework [7] and on standard graph theory (Vizing's theorem, spanning trees). No new physical or formal entities are postulated.

assumptions (4)

standard math Vizing's theorem: every graph has an edge-coloring with at most Delta+1 colors.
Used in Definition 4.8 (support-dilation) and Definition 4.14 (directed semaphore) to perturb labels by c(e)*epsilon so adjacent edges get distinct labels.
domain assumption Results and lemmas from Casteigts, Corsini, and Sarkar [7], including their dilation, saturation, and semaphore constructions and Lemma 1 on distance-two vertices in undirected strict simple graphs.
The entire framework of settings and equivalence notions is adopted from [7]; Theorem 3.1 cites [7, Lemma 1] directly, and Theorem 4.15 is proven by reference to [7, Theorem 2].
domain assumption The standard temporal graph model: a temporal path is a sequence of temporal edges whose time labels are non-decreasing (strictly increasing in strict settings), and the reachability graph records all temporal paths.
Stated in Section 2; all results are relative to this model.
standard math Every connected graph contains a spanning tree, and any connected component of a snapshot can be represented by such a tree.
Reachability-dilation (Definition 4.10) replaces each strongly connected component with a bidirected spanning tree; Lemma 4.11 then provides the temporal connectivity.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Simple, Strict, Proper, and Directed: Comparing Reachability in Directed and Undirected Temporal Graphs." pith.science (2026). https://pith.science/paper/VOLN3557

@misc{pith2026250111697,
  author       = {Pith},
  title        = {Pith review of: Simple, Strict, Proper, and Directed: Comparing Reachability in Directed and Undirected Temporal Graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VOLN3557}},
  note         = {Machine review of arXiv:2501.11697}
}

read the original abstract

We present the first comprehensive analysis of temporal settings for directed temporal graphs, fully resolving their hierarchy with respect to support, reachability, and induced-reachability equivalence. These notions, introduced by Casteigts, Corsini, and Sarkar, capture different levels of equivalence between temporal graph classes. Their analysis focused on undirected graphs under three dimensions: strict vs. non-strict (whether times along paths strictly increase), proper vs. arbitrary (whether adjacent edges can appear simultaneously), and simple vs. multi-labeled (whether an edge can appear multiple times). In this work, we extend their framework by adding the fundamental distinction of directed vs. undirected. Our results reveal a single-strand hierarchy for directed graphs, with strict & simple being the most expressive class and proper & simple the least expressive. In contrast, undirected graphs form a two-strand hierarchy, with strict & multi-labeled being the most expressive and proper & simple the least expressive. The two strands are formed by the non-strict & simple and the strict & simple class, which we show to be incomparable. In addition to examining the internal hierarchies of directed and of undirected graph classes, we compare the two. We show that each undirected class can be transformed into its directed counterpart under reachability equivalence, while no directed class can be transformed into any undirected one. Our findings have significant implications for the study of computational problems on temporal graphs. Positive results in more expressive graph classes extend to weaker classes as long as the problem is independent under reachability equivalence. Conversely, hardness results for a less expressive class propagate to stronger classes. We hope these findings will inspire a unified approach for analyzing temporal graphs under the different settings.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

21 extracted references · 11 canonical work pages

[7]

Simple, strict, proper, happy: A study of reachability in temporal graphs

Arnaud Casteigts, Timothée Corsini, and Writika Sarkar. Simple, strict, proper, happy: A study of reachability in temporal graphs. Theoretical Computer Science, 991: 0 114434, April 2024 a . ISSN 0304-3975. doi:10.1016/j.tcs.2024.114434. URL https://www.sciencedirect.com/science/article/pii/S0304397524000495

work page arXiv 2024
[1]

Vulnerability of scheduled networks and a generalization of menger's theorem

Kenneth A Berman. Vulnerability of scheduled networks and a generalization of menger's theorem. Networks: An International Journal, 28 0 (3): 0 125--134, 1996

work page 1996
[2]

Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks

Sandeep Bhadra and Afonso Ferreira. Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks. In Ad-Hoc, Mobile, and Wireless Networks: Second International Conference, ADHOC-NOW2003, Montreal, Canada, October 8-10, 2003. Proceedings 2, pages 259--270. Springer, 2003

work page 2003
[3]

A problem with telephones

Richard T Bumby. A problem with telephones. SIAM Journal on Algebraic Discrete Methods, 2 0 (1): 0 13--18, 1981

work page 1981
[4]

In search of the lost tree: Hardness and relaxation of spanning trees in temporal graphs, December 2023

Arnaud Casteigts and Timothée Corsini. In search of the lost tree: Hardness and relaxation of spanning trees in temporal graphs, December 2023. URL http://arxiv.org/abs/2312.06260. arXiv:2312.06260 [cs]

arXiv 2023
[5]

Time- Varying Graphs and Dynamic Networks , February 2012

Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. Time- Varying Graphs and Dynamic Networks , February 2012. URL http://arxiv.org/abs/1012.0009. arXiv:1012.0009 [physics]

arXiv 2012
[6]

Sharp Thresholds in Random Simple Temporal Graphs

Arnaud Casteigts, Michael Raskin, Malte Renken, and Viktor Zamaraev. Sharp Thresholds in Random Simple Temporal Graphs . In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science ( FOCS ) , pages 319--326, Denver, CO, USA, February 2022. IEEE. ISBN 978-1-66542-055-6. doi:10.1109/FOCS52979.2021.00040. URL https://ieeexplore.ieee.org/document/9719741/

arXiv 2021
[8]

Distance to Transitivity: New Parameters for Taming Reachability in Temporal Graphs

Arnaud Casteigts, Nils Morawietz, and Petra Wolf. Distance to Transitivity: New Parameters for Taming Reachability in Temporal Graphs . In Rastislav Kr\' a lovi c and Anton \' n Ku c era, editors, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), volume 306 of Leibniz International Proceedings in Informatics (LIPIcs...

doi:10.4230/l 2024

Show all 21 references

[9]

On Inefficiently Connecting Temporal Networks

Esteban Christiann, Eric Sanlaville, and Jason Schoeters. On Inefficiently Connecting Temporal Networks . LIPIcs, Volume 292, SAND 2024, 292: 0 8:1--8:19, 2024. ISSN 1868-8969. doi:10.4230/LIPICS.SAND.2024.8. URL https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND....

2024 doi
[10]

On computing large temporal (unilateral) connected components

Isnard Lopes Costa, Raul Lopes, Andrea Marino, and Ana Paula Couto da Silva. On computing large temporal (unilateral) connected components. In International Workshop on Combinatorial Algorithms, 2023. URL https://api.semanticscholar.org/CorpusID:257102754

2023
[11]

Being an influencer is hard: The complexity of influence maximization in temporal graphs with a fixed source

Argyrios Deligkas, Michelle Döring, Eduard Eiben, Tiger-Lily Goldsmith, and George Skretas. Being an influencer is hard: The complexity of influence maximization in temporal graphs with a fixed source. Information and Computation, 299: 0 105171, 2024. ISSN 0890-5401. doi:https...

2024
[12]

Temporal graph classes: A view through temporal separators

Till Fluschnik, Hendrik Molter, Rolf Niedermeier, Malte Renken, and Philipp Zschoche. Temporal graph classes: A view through temporal separators. Theoretical Computer Science, 806: 0 197--218, 2020. URL https://www.sciencedirect.com/science/article/pii/S0304397519301975. Publi...

2020
[13]

Delay- Robust Routes in Temporal Graphs , January 2022

Eugen Füchsle, Hendrik Molter, Rolf Niedermeier, and Malte Renken. Delay- Robust Routes in Temporal Graphs , January 2022. URL http://arxiv.org/abs/2201.05390. arXiv:2201.05390 [cs]

2022 arXiv
[14]

Minimal strong digraphs

Jes \'u s Garc \' a-L \'o pez and Carlos Mariju \'a n. Minimal strong digraphs. Discrete Mathematics, 312 0 (4): 0 737--744, 2012

2012
[15]

Göbel, J

F. Göbel, J. Orestes Cerdeira, and H. J. Veldman. Label-connected graphs and the gossip problem. Discrete Mathematics, 87 0 (1): 0 29--40, January 1991. ISSN 0012-365X. doi:10.1016/0012-365X(91)90068-D. URL https://www.sciencedirect.com/science/article/pii/0012365X9190068D

1991
[16]

Connectivity and Inference Problems for Temporal Networks

David Kempe, Jon Kleinberg, and Amit Kumar. Connectivity and Inference Problems for Temporal Networks . Journal of Computer and System Sciences, 64 0 (4): 0 820--842, June 2002. ISSN 0022-0000. doi:10.1006/jcss.2002.1829. URL https://www.sciencedirect.com/science/article/pii/S...

2002
[17]

Mertzios, Hendrik Molter, Rolf Niedermeier, and Philipp Zschoche

Nina Klobas, George B. Mertzios, Hendrik Molter, Rolf Niedermeier, and Philipp Zschoche. Interference-free walks in time: temporally disjoint paths. Autonomous Agents and Multi-Agent Systems, 37 0 (1): 0 1, June 2023. ISSN 1387-2532, 1573-7454. doi:10.1007/s10458-022-09583-5. ...

2023 doi
[18]

In Which Graph Structures Can We Efficiently Find Temporally Disjoint Paths and Walks ?, January 2023

Pascal Kunz, Hendrik Molter, and Meirav Zehavi. In Which Graph Structures Can We Efficiently Find Temporally Disjoint Paths and Walks ?, January 2023. URL http://arxiv.org/abs/2301.10503. arXiv:2301.10503 [cs]

2023 arXiv
[19]

Mertzios, Hendrik Molter, Malte Renken, Paul G

George B. Mertzios, Hendrik Molter, Malte Renken, Paul G. Spirakis, and Philipp Zschoche. The Complexity of Transitively Orienting Temporal Graphs , July 2023. URL http://arxiv.org/abs/2102.06783. arXiv:2102.06783 [cs]

2023 arXiv
[20]

A theoretical and experimental study of a new algorithm for minimum cost flow in dynamic graphs

Mathilde Vernet, Maciej Drozdowski, Yoann Pigné, and Eric Sanlaville. A theoretical and experimental study of a new algorithm for minimum cost flow in dynamic graphs. Discrete Applied Mathematics, 296: 0 203--216, June 2021. ISSN 0166-218X. doi:10.1016/j.dam.2019.12.012. URL h...

2021 doi
[21]

Xuan, Afonso Ferreira, and Aubin Jarry

B. Xuan, Afonso Ferreira, and Aubin Jarry. Computing shortest, fastest, and foremost journeys in dynamic networks. October 2002

2002

Pith tools

Reviewed August 10, 2026 · model on record in the stance chip above.

[1] [7]

Simple, strict, proper, happy: A study of reachability in temporal graphs

Arnaud Casteigts, Timothée Corsini, and Writika Sarkar. Simple, strict, proper, happy: A study of reachability in temporal graphs. Theoretical Computer Science, 991: 0 114434, April 2024 a . ISSN 0304-3975. doi:10.1016/j.tcs.2024.114434. URL https://www.sciencedirect.com/science/article/pii/S0304397524000495

work page arXiv 2024

[2] [1]

Vulnerability of scheduled networks and a generalization of menger's theorem

Kenneth A Berman. Vulnerability of scheduled networks and a generalization of menger's theorem. Networks: An International Journal, 28 0 (3): 0 125--134, 1996

work page 1996

[3] [2]

Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks

Sandeep Bhadra and Afonso Ferreira. Complexity of connected components in evolving graphs and the computation of multicast trees in dynamic networks. In Ad-Hoc, Mobile, and Wireless Networks: Second International Conference, ADHOC-NOW2003, Montreal, Canada, October 8-10, 2003. Proceedings 2, pages 259--270. Springer, 2003

work page 2003

[4] [3]

A problem with telephones

Richard T Bumby. A problem with telephones. SIAM Journal on Algebraic Discrete Methods, 2 0 (1): 0 13--18, 1981

work page 1981

[5] [4]

In search of the lost tree: Hardness and relaxation of spanning trees in temporal graphs, December 2023

Arnaud Casteigts and Timothée Corsini. In search of the lost tree: Hardness and relaxation of spanning trees in temporal graphs, December 2023. URL http://arxiv.org/abs/2312.06260. arXiv:2312.06260 [cs]

arXiv 2023

[6] [5]

Time- Varying Graphs and Dynamic Networks , February 2012

Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. Time- Varying Graphs and Dynamic Networks , February 2012. URL http://arxiv.org/abs/1012.0009. arXiv:1012.0009 [physics]

arXiv 2012

[7] [6]

Sharp Thresholds in Random Simple Temporal Graphs

Arnaud Casteigts, Michael Raskin, Malte Renken, and Viktor Zamaraev. Sharp Thresholds in Random Simple Temporal Graphs . In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science ( FOCS ) , pages 319--326, Denver, CO, USA, February 2022. IEEE. ISBN 978-1-66542-055-6. doi:10.1109/FOCS52979.2021.00040. URL https://ieeexplore.ieee.org/document/9719741/

arXiv 2021

[8] [8]

Distance to Transitivity: New Parameters for Taming Reachability in Temporal Graphs

Arnaud Casteigts, Nils Morawietz, and Petra Wolf. Distance to Transitivity: New Parameters for Taming Reachability in Temporal Graphs . In Rastislav Kr\' a lovi c and Anton \' n Ku c era, editors, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024), volume 306 of Leibniz International Proceedings in Informatics (LIPIcs...

doi:10.4230/l 2024