Temporal Explorability Games

Nicolas Mazzocchi; Patrick Totzke; Pete Austin; Sougata Bose

REVIEW 1 major objections 3 minor 14 references

Temporal Explorability Games

T0 review · 1 major / 3 minor · reviewed 2026-08-11 · deepseek-v4-flash

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

Pith's one-line read A lone player who must reach a target in a succinctly represented temporal graph already faces a PSPACE-hard problem, and the same hardness is claimed for exploring the whole graph.

desk verdict Two strong lower bounds, but the 'and thus explorability' step is unproved for temporal graphs, so the headline one-player symbolic explorability result overclaims. read the letter →

arxiv 2412.16328 v3 pith:7GMJKGIS submitted 2024-12-20 cs.GT cs.LO

Pete Austin , Nicolas Mazzocchi , Sougata Bose , Patrick Totzke This is my paper · ORCID

classification cs.GTcs.LO MSC 91A4391A5068Q1568Q17

keywords temporalgraphsexplorabilitygamesreachabilitygeneralizedPSPACE-completenessPresburgerarithmeticQBFreductionturn-based

topics P versus NP

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

Explorability games ask whether a player can force a walk that visits every vertex of a graph whose edges open and close on a discrete time schedule; these games model dynamic networks and reactive systems where every state must eventually be covered. The paper's thesis is that the complexity of this question is governed by two independent factors: whether an adversary controls some vertices, and whether the schedule is written out edge-by-edge or compressed into arithmetic formulas. On static graphs, exploring is exactly as hard as reaching: NL-complete for one player and P-complete for two players. On explicitly timed graphs, one-player exploration jumps to NP-complete and two-player exploration to PSPACE-complete. The headline result is that on symbolically compressed schedules, even one-player reachability — and, the paper asserts, exploration — is PSPACE-hard, with one-player cases in PSPACE and two-player explorability lying between PSPACE-hard and EXP.

What carries the argument

The carrying object is the expansion of a temporal graph: a static graph whose vertices are (vertex, time) pairs and whose edges exist exactly when the original edge is available at that time. For explicitly encoded schedules the expansion is only polynomially larger, so upper bounds transfer from static generalized reachability games. The lower-bound mechanism is a Presburger-guarded gadget — logical conditions over integer addition that can inspect the bits of the current time — that reads four-bit sectors of the binary representation of the current time as QBF variable assignments; existential quantifier vertices offer a self-loop that lets the player spend time to choose a bit, and universal quantifier vertices react to bit overflows by backtracking through earlier sectors, giving one player's simple path-finding the power to simulate adversarial choice. The explicit two-player lower bound instead uses a time-bounded flooding phase after the QBF game, during which exactly enough steps remain to visit the leftover vertices if and only if the formula was satisfiable.

What would settle it

Apply the Lemma 3 construction to the temporal arena with vertices $s,t,u,v$ where $s\to t$, $u\to s$, and $v\to s$ are each available only at time $0$. Player 1 reaches $t$ from $s$ in the original arena, but in the constructed arena the only exits from $u$ and $v$ are still available only at time $0$, and by the time the explorer can leave $t$ those times have passed; hence no play visits both $u$ and $v$, so the explorability game is lost. This is the minimal experiment showing the log-space reachability-to-explorability transfer does not extend to temporal graphs.

Watch

Extended reading notes

Core claim

The central claim is a complexity trichotomy: explorability is no harder than reachability on static graphs, yet on temporal graphs it is as hard as generalized reachability, and on symbolically represented temporal graphs even a single player's reachability problem is PSPACE-hard. The paper's main construction reduces quantified Boolean formulas to one-player reachability on a symbolic temporal graph. Time itself is the memory: the binary expansion of the current time is divided into four-bit sectors, one sector per quantifier, and the player chooses assignments to existential variables by how long she waits on a self-loop, while universal quantifiers are simulated by a cascade of bit overflows that drives the walk backward through earlier sectors. Since the paper asserts reachability reduces in logarithmic space to explorability, it concludes that one-player symbolic explorability and generalized reachability are PSPACE-complete, and that two-player symbolic explorability is PSPACE-hard and solvable in exponential time.

Load-bearing premise

The load-bearing premise is that every reachability game on a temporal graph can be converted in logarithmic space into an explorability game on a temporal graph; the paper proves this reduction only for static graphs, where delaying a move by one step does not change which target vertices are reachable, while on time-sensitive edges the delay can destroy a path.

Editorial extensions

If this is right

One-player reachability, explorability, and generalized reachability on symbolically represented temporal graphs are PSPACE-complete (Corollary 14), so no polynomial-time solver exists unless the polynomial hierarchy collapses.
On explicitly represented temporal graphs, one-player explorability is NP-complete and two-player explorability is PSPACE-complete, exactly matching generalized reachability.
If waiting is allowed on symbolic temporal graphs, all three one-player objectives drop to NP-complete, isolating the forced-move rule as the source of the jump in hardness.
The number of temporal edges can tune hardness to a fixed level of the polynomial hierarchy: with $K \geq 2\lceil m/2\rceil + 9\lfloor m/2\rfloor + 1$ temporal edges, one-player symbolic reachability is $\Sigma^\mathrm{P}_m$-hard (Corollary 10).
Two-player symbolic explorability and generalized reachability lie between PSPACE-hard and EXP; the paper conjectures that PSPACE membership holds.

Reading between the lines

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

Editorial: the reachability-to-explorability transfer used to carry Theorem 9 to Corollary 14 is proved only for static graphs in Lemma 3, where inserting a new vertex delays arrival by one step without changing reachability; on temporal graphs that delay can make an edge expire before it is used, so the transfer is an unproved premise rather than a demonstrated corollary.
Editorial: the bit-sector reduction suggests a general recipe—whenever a monotonically advancing clock can be read by a Presburger predicate, carries between bit positions give a free counter-machine simulation, so similar PSPACE lower bounds may apply to other objectives on succinctly specified dynamic graphs.
Editorial: Corollary 10's edge-count bound $K \geq 2\lceil m/2\rceil + 9\lfloor m/2\rfloor + 1$ is an artifact of the specific gadgets; an obvious test is to search for constructions with fewer temporal edges that still reach each level of the polynomial hierarchy.
Editorial: a concrete next step suggested by the gap is to decide whether two-player symbolic explorability is in PSPACE by exploiting the ultimately periodic structure of Presburger edge sets, or to prove EXP-hardness by encoding recoverable information into timestamps.

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

Read the temporal explorability paper. Main takeaway: the two genuinely new lower bounds are worth taking seriously, but the abstract's 'and thus explorability' is a bridge too far. Theorem 9 (one-player symbolic reachability is PSPACE-hard) is a real result, and Theorem 8 (two-player explicit explorability PSPACE-complete) looks correct and interesting. The Presburger time-encoding gadget in Theorem 9 is clever; it encodes QBF valuations in the bits of elapsed time and uses a cascade of backtracking to simulate universal quantifiers. That's a solid contribution and likely to be used elsewhere.

The static-graph classification (Theorem 5) is straightforward but correct, and the explicit temporal results (Theorems 7, 8) fill a gap. The upper bounds in Theorem 13 are also useful.

Where the paper goes soft: the claim that reachability reduces to explorability 'straightforwardly in logarithmic space' is only proved for static arenas (Lemma 3). The construction inserts a new vertex on every edge, which delays arrival at the target by one time step. On a temporal graph with edge availability at isolated times, that shift breaks the reduction. The paper never gives a temporal version, yet the abstract and Corollary 14 use exactly this transfer to conclude that one-player symbolic explorability is PSPACE-hard. So the PSPACE-completeness of one-player symbolic explorability is not established by the results in this paper. It may be true, but the proof as written has a hole. This is not a minor footnote; it's the difference between 'one-player symbolic reachability PSPACE-hard' and 'one-player symbolic explorability PSPACE-complete.' The upper bound (PSPACE) holds, so the gap is only on the lower-bound side.

The rest of the paper seems sound. The QBF reduction for two-player explicit explorability is intricate; I did not find a flaw in the flooding-phase argument. The related work and discussion of the EXP gap are honest and well-placed.

My recommendation: send to peer review with a request for major revision. The authors need either a time-preserving reduction from reachability to explorability on temporal graphs, or they should state the one-player symbolic explorability hardness as an open problem and adjust the abstract and Corollary 14 accordingly. The paper has enough solid new material to justify a revise-and-resubmit.

Referee Report

1 major / 3 minor

Summary. This paper studies the computational complexity of solving explorability games on temporal graphs, where Player 1 wins if the play visits every vertex. The authors consider one- and two-player variants and three input representations: static graphs, explicitly represented temporal graphs, and symbolically represented temporal graphs (edge availability given by existential Presburger formulas). They prove that static explorability is NL-complete (one-player) and P-complete (two-player); explicit temporal explorability is NP-complete (one-player) and PSPACE-complete (two-player); and symbolic one-player reachability is PSPACE-hard. They also provide PSPACE and EXP upper bounds for one- and two-player symbolic generalized reachability. The paper's headline claim is that the PSPACE-hardness of one-player symbolic reachability transfers "and thus" to explorability and generalized reachability, yielding PSPACE-completeness for all three objectives in the one-player symbolic case. The transfer is the point on which the paper needs additional support.

Significance. The paper makes several solid contributions: the static-game classification (Theorem 5), the two-player explicit temporal PSPACE-completeness (Theorem 8), the one-player symbolic reachability lower bound (Theorem 9), and the EXP upper bound for symbolic generalized reachability (Theorem 13) are all nontrivial and, apart from local issues, are argued carefully. The bit-encoding gadget in Theorem 9 is particularly interesting and is the strongest technical result in the paper. If the missing reachability-to-explorability transfer for temporal graphs can be provided, the claimed PSPACE-completeness of one-player symbolic explorability and generalized reachability would round out a clean complexity map. As it stands, that part of the abstract and Corollary 14 goes beyond what is proved, so the significance of the paper as a whole is conditional.

major comments (1)

[Corollary 14, Abstract, Section 1, Lemma 3] The claim that one-player symbolic explorability and generalized reachability are PSPACE-complete is asserted to follow from Theorem 9 via the statement that reachability games reduce in logarithmic space to explorability games. The only reduction supplied for that implication is Lemma 3, which is proved for static arenas: it inserts a new vertex [v,u] between every pair v,u and resets to s. This construction is time-sensitive and does not extend to temporal graphs, because inserting a vertex shifts all subsequent arrival times and therefore changes which temporally available edges can be taken. For example, if the original arena has edges s->u at time 0 and u->t at time 1, the modified arena makes the token arrive at u at time 2, so the edge u->t is missed. The observation in Section 4 that explorability on a temporal graph corresponds to generalized reachability on its expansion is in the wrong direction for this purpose: it shows that explorability reduces to generalized reachability, not that reachability hardness transfers to explorability. Since explorability is a special case of generalized reachability, hardness of reachability does not automatically give hardness of either objective. No temporal version of Lemma 3, and no direct QBF encoding of explorability on symbolic temporal graphs, is provided. Therefore the PSPACE-hardness of one-player symbolic explorability and generalized reachability is not established by the arguments in the paper; this is load-bearing for the headline claim that one-player reachability hardness carries over "and thus" to explorability.

minor comments (3)

[Theorem 8, flooding phase] The timing of the flooding phase is inconsistent. The text says the phase lasts exactly n-1 steps starting at time k+2n+2 and that all edges become unavailable from k+3n+1 onwards, but it defines the edge availability as [k+2n+2, k+3n+1]; this interval contains n time points, not n-1, and the caption of Figure 4 uses the interval (k+2n+1, k+3n+1). Please make the bounds and the count consistent.
[Definition 1 and Theorem 9] Definition 1 defines the horizon as the largest finite time at which an edge is available, but Theorem 9 writes h(G_Phi)=2^{4n} while the construction uses times theta in {0,...,2^{4n}-1}; the paper also says a witnessing path has exactly 2^{4n} edges. The off-by-one between these quantities should be reconciled.
[References] References [30] and [31] are the same bibliographic entry (Michail, An Introduction to Temporal Graphs) and should be merged; the first occurrence in Section 1 and the citation in the Conclusion should use a single number.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: hardness derivations are QBF reductions and upper bounds use external algorithms; the disputed temporal reachability-to-explorability transfer is an unproved reduction, not a definitional or fitted equivalence.

full rationale

The paper's main derivations are self-contained reductions from QBF or from known hard problems, not conclusions that assume their own target. Theorem 9 proves one-player symbolic temporal reachability PSPACE-hard by an explicit QBF encoding in which time bits encode variable valuations and backtracking enforces universal quantifiers; the if-and-only-if proof is carried out by induction on the quantifier structure. Theorem 8 similarly gives a direct QBF reduction for two-player explicit explorability. Upper bounds rest on the expansion construction, semilinearity of Presburger-definable sets, and independent results such as Fijalkow and Horn's PSPACE algorithm for generalized reachability. The only potentially vulnerable step is the paper's assertion that reachability hardness carries over to explorability ('reachability and thus explorability'), for which the supplied reduction, Lemma 3, is proved only for static graphs and does not obviously extend to temporal schedules. That is a correctness or proof-gap concern, not circularity: the claim is not obtained by defining reachability in terms of explorability, by fitting parameters, or by citing the authors' own unverified theorem. No circular step can be exhibited by quote and reduction, so the circularity score is 0.

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

The paper introduces no physical entities or fitted constants. It rests on standard complexity-theoretic theorems and one unproved reduction premise (the temporal reachability-to-explorability transfer).

assumptions (6)

domain assumption In the game model, a token must move along an available edge at every integer time step; waiting is not allowed except by encoding self-loops.
Definition 1 and the expansion construction in Section 2; this makes winning plays finite-horizon and is essential for the PSPACE upper bounds and the flooding gadget.
standard math QBF satisfiability is PSPACE-complete.
Used for the lower bounds in Theorems 8 and 9.
standard math Presburger-definable subsets of N are ultimately periodic with base and period at most exponential in formula size.
Invoked in Theorem 13 to bound b and p for the exponential-size reachability-game construction; cited from [21].
standard math Reachability games on static graphs are P-complete (two-player) and NL-complete (one-player).
Used in Theorems 5 and 6; standard results cited as [1] and [6].
standard math Generalized reachability games on static graphs are PSPACE-complete (two-player) and NP-complete (one-player).
Used in Theorem 6 and upper bound of Theorem 8; cited from [18].
ad hoc to paper Reachability games on temporal graphs reduce in logarithmic space to explorability games on temporal graphs.
Stated in the Introduction as 'straightforwardly and in logarithmic space' but only proved for static graphs in Lemma 3. The temporal version is used to derive PSPACE-hardness of one-player symbolic explorability in Corollary 14 and is not established; the static construction fails on time-sensitive edges.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Temporal Explorability Games." pith.science (2026). https://pith.science/paper/7GMJKGIS

@misc{pith2026241216328,
  author       = {Pith},
  title        = {Pith review of: Temporal Explorability Games},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7GMJKGIS}},
  note         = {Machine review of arXiv:2412.16328}
}

read the original abstract

Temporal graphs extend ordinary graphs with discrete time that affects the availability of edges. We consider solving games played on temporal graphs where one player aims to explore the graph, i.e., visit all vertices. The complexity depends majorly on two factors: the presence of an adversary and how edge availability is specified. We demonstrate that on static graphs, where edges are always available, solving explorability games is just as hard as solving reachability games. In contrast, on temporal graphs, the complexity of explorability coincides with generalized reachability (NP-complete for one-player and PSPACE- complete for two player games). We further show that if temporal graphs are given symbolically, even one-player reachability and thus explorability and generalized reachability games are PSPACE-hard. For one player, all these are also solvable in PSPACE and for two players, they are in PSPACE, EXP and EXP, respectively.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

14 extracted references · 7 canonical work pages

[11]

org/10.1016/j.jcss.2021.03.005

doi:https://doi. org/10.1016/j.jcss.2021.03.005. 29 George B. Mertzios, Sotiris Nikoletseas, Christoforos Raptopoulos, and Paul G. Spirakis. Brief Announcement: On the Existence ofδ-Temporal Cliques in Random Simple Temporal Graphs. In3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024), volume P. Austin, S. Bose, N. Mazzocchi, and P. ...

work page doi:10.1016/j.jcss.2021.03.005 2021
[13]

Pnueli and R

35 A. Pnueli and R. Rosner. On the synthesis of a reactive module. InAnnual Symposium on Principles of Programming Languages, POPL ’89, page 179–190. Association for Computing Machinery, 1989.doi:10.1145/75277.75293. 36 Amir Pnueli. The temporal logic of programs. InAnnual Symposium on Foundations of Computer Science, SFCS ’77, page 46–57. IEEE Computer S...

arXiv 1989
[1994]

Complexity of subcases of presburger arithmetic.Transactions of the American Mathematical Society, 284(1):203–218, 1984.doi:10.2307/1999283

38 Bruno Scarpellini. Complexity of subcases of presburger arithmetic.Transactions of the American Mathematical Society, 284(1):203–218, 1984.doi:10.2307/1999283. 39 Yuejiao Wang, Dajun Daniel Zeng, Qingpeng Zhang, Pengfei Zhao, Xiaoli Wang, Quanyi Wang, Yin Luo, and Zhidong Cao. Adaptively temporal graph convolution model for epidemic prediction of multi...

work page doi:10.2307/1999283 1984
[2002]

Gusev, Dmitriy Malyshev, and Viktor Zamaraev

2 Duncan Adamson, Vladimir V. Gusev, Dmitriy Malyshev, and Viktor Zamaraev. Faster Exploration of Some Temporal Graphs. In1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022), volume 221 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:10. Schloss Dagstuhl – Leibniz-Zentrum für Informatik,

work page 2022
[2007]

Distributed computation in dynamic networks

24 Fabian Kuhn, Nancy Lynch, and Rotem Oshman. Distributed computation in dynamic networks. InSymposium on Theory of Computing, STOC ’10, page 513–522. Association for Computing Machinery, 2010.doi:10.1145/1806689.1806760. 25 Oded Maler, Amir Pnueli, and Joseph Sifakis. On the synthesis of discrete controllers for timed systems. InInternational Symposium ...

arXiv 2010
[2009]

The complexity of online graph games

20 Janosch Fuchs, Christoph Grüne, and Tom Janßen. The complexity of online graph games. In SOFSEM 2024: Theory and Practice of Computer Science, pages 269–282. Springer Nature Switzerland,

work page 2024
[2011]

Mertzios, Hendrik Molter, Rolf Niedermeier, Viktor Zamaraev, and Philipp Zschoche

27 George B. Mertzios, Hendrik Molter, Rolf Niedermeier, Viktor Zamaraev, and Philipp Zschoche. Computing maximum matchings in temporal graphs.Journal of Computer and System Sciences, 137:1–19, 2023.doi:https://doi.org/10.1016/j.jcss.2023.04.005. 28 George B. Mertzios, Hendrik Molter, and Viktor Zamaraev. Sliding window temporal graph coloring.Journal of ...

doi:10.1016/j.jcss.2023.04.005 2023
[2012]

On temporal graph exploration

15 Thomas Erlebach, Michael Hoffmann, and Frank Kammer. On temporal graph exploration. Journal of Computer and System Sciences, 119:1–18, 2021.doi:https://doi.org/10.1016/ j.jcss.2021.01.005. 16 John Fearnley and Marcin Jurdziński. Reachability in two-clock timed automata is pspace- complete. InAutomata, Languages, and Programming, pages 212–223. Springer...

work page 2021

Show all 14 references

[2013]

Games on graphs, 2023.arXiv:2305.10546

17 Nathanaël Fijalkow, Nathalie Bertrand, Patricia Bouyer-Decitre, Romain Brenguier, Arnaud Carayol, John Fearnley, Hugo Gimbert, Florian Horn, Rasmus Ibsen-Jensen, Nicolas Markey, Benjamin Monmege, Petr Novotný, Mickael Randour, Ocan Sankur, Sylvain Schmitz, Olivier Serre, an...

2023 arXiv
[2014]

Spirakis

33 Othon Michail and Paul G. Spirakis. Traveling salesman problems in temporal graphs. Theoretical Computer Science, 634:1–23, 2016.doi:https://doi.org/10.1016/j.tcs.2016. 04.006. 34 Andrzej Pelc. Explorable families of graphs. InStructural Information and Communication Comple...

2016 doi
[2018]

URL: https://www.sciencedirect.com/science/article/ pii/S0304397516302535,doi:https://doi.org/10.1016/j.tcs.2016.06.017

Reachability Problems 2014: Special Issue. URL: https://www.sciencedirect.com/science/article/ pii/S0304397516302535,doi:https://doi.org/10.1016/j.tcs.2016.06.017. 16 Temporal Explorability Games 12 Jean-Lou De Carufel, Paola Flocchini, Nicola Santoro, and Frédéric Simard. Cop...

2014 doi
[2021]

Henzinger, and Vinayak S

9 Krishnendu Chatterjee, Thomas A. Henzinger, and Vinayak S. Prabhu. Timed Parity Games: Complexity and Robustness.Logical Methods in Computer Science, Volume 7, Issue 4, December 2011.doi:10.2168/LMCS-7(4:8)2011. 10 Hongjiang Chen, Pengfei Jiao, Huijun Tang, and Huaming Wu. T...

2011 doi
[2022]

3 Eleni C

doi:10.4230/LIPIcs.SAND.2022.5. 3 Eleni C. Akrida, George B. Mertzios, Paul G. Spirakis, and Christoforos Raptopoulos. The temporal explorer who returns to the base.Journal of Computer and System Sciences, 120:179–193, 2021.doi:https://doi.org/10.1016/j.jcss.2021.04.001. 4 Ele...

2022 doi
[2023]

Minimizing reachability times on temporal graphs via shifting labels

13 Argyrios Deligkas, Eduard Eiben, and George Skretas. Minimizing reachability times on temporal graphs via shifting labels. InProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI-23, pages 5333–5340. International Joint Confer- en...

2023 doi

Pith tools

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

[1] [11]

org/10.1016/j.jcss.2021.03.005

doi:https://doi. org/10.1016/j.jcss.2021.03.005. 29 George B. Mertzios, Sotiris Nikoletseas, Christoforos Raptopoulos, and Paul G. Spirakis. Brief Announcement: On the Existence ofδ-Temporal Cliques in Random Simple Temporal Graphs. In3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2024), volume P. Austin, S. Bose, N. Mazzocchi, and P. ...

work page doi:10.1016/j.jcss.2021.03.005 2021

[2] [13]

Pnueli and R

35 A. Pnueli and R. Rosner. On the synthesis of a reactive module. InAnnual Symposium on Principles of Programming Languages, POPL ’89, page 179–190. Association for Computing Machinery, 1989.doi:10.1145/75277.75293. 36 Amir Pnueli. The temporal logic of programs. InAnnual Symposium on Foundations of Computer Science, SFCS ’77, page 46–57. IEEE Computer S...

arXiv 1989

[3] [1994]

Complexity of subcases of presburger arithmetic.Transactions of the American Mathematical Society, 284(1):203–218, 1984.doi:10.2307/1999283

38 Bruno Scarpellini. Complexity of subcases of presburger arithmetic.Transactions of the American Mathematical Society, 284(1):203–218, 1984.doi:10.2307/1999283. 39 Yuejiao Wang, Dajun Daniel Zeng, Qingpeng Zhang, Pengfei Zhao, Xiaoli Wang, Quanyi Wang, Yin Luo, and Zhidong Cao. Adaptively temporal graph convolution model for epidemic prediction of multi...

work page doi:10.2307/1999283 1984

[4] [2002]

Gusev, Dmitriy Malyshev, and Viktor Zamaraev

2 Duncan Adamson, Vladimir V. Gusev, Dmitriy Malyshev, and Viktor Zamaraev. Faster Exploration of Some Temporal Graphs. In1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022), volume 221 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 5:1–5:10. Schloss Dagstuhl – Leibniz-Zentrum für Informatik,

work page 2022

[5] [2007]

Distributed computation in dynamic networks

24 Fabian Kuhn, Nancy Lynch, and Rotem Oshman. Distributed computation in dynamic networks. InSymposium on Theory of Computing, STOC ’10, page 513–522. Association for Computing Machinery, 2010.doi:10.1145/1806689.1806760. 25 Oded Maler, Amir Pnueli, and Joseph Sifakis. On the synthesis of discrete controllers for timed systems. InInternational Symposium ...

arXiv 2010

[6] [2009]

The complexity of online graph games

20 Janosch Fuchs, Christoph Grüne, and Tom Janßen. The complexity of online graph games. In SOFSEM 2024: Theory and Practice of Computer Science, pages 269–282. Springer Nature Switzerland,

work page 2024

[7] [2011]

Mertzios, Hendrik Molter, Rolf Niedermeier, Viktor Zamaraev, and Philipp Zschoche

27 George B. Mertzios, Hendrik Molter, Rolf Niedermeier, Viktor Zamaraev, and Philipp Zschoche. Computing maximum matchings in temporal graphs.Journal of Computer and System Sciences, 137:1–19, 2023.doi:https://doi.org/10.1016/j.jcss.2023.04.005. 28 George B. Mertzios, Hendrik Molter, and Viktor Zamaraev. Sliding window temporal graph coloring.Journal of ...

doi:10.1016/j.jcss.2023.04.005 2023

[8] [2012]

On temporal graph exploration

15 Thomas Erlebach, Michael Hoffmann, and Frank Kammer. On temporal graph exploration. Journal of Computer and System Sciences, 119:1–18, 2021.doi:https://doi.org/10.1016/ j.jcss.2021.01.005. 16 John Fearnley and Marcin Jurdziński. Reachability in two-clock timed automata is pspace- complete. InAutomata, Languages, and Programming, pages 212–223. Springer...

work page 2021