Tight Bounds on Window Size and Time for Single-Agent Graph Exploration under T-Interval Connectivity

Junya Nakamura; Koichi Wada; Masahiro Shibata; Naoki Kitamura; S\'ebastien Tixeuil; Toshimitsu Masuzawa; Yuichi Sudo

arxiv: 2604.04619 · v1 · submitted 2026-04-06 · 💻 cs.DC

Tight Bounds on Window Size and Time for Single-Agent Graph Exploration under T-Interval Connectivity

Yuichi Sudo , Naoki Kitamura , Masahiro Shibata , Junya Nakamura , S\'ebastien Tixeuil , Toshimitsu Masuzawa , Koichi Wada This is my paper

Pith reviewed 2026-05-10 19:23 UTC · model grok-4.3

classification 💻 cs.DC

keywords T-interval connectivitydynamic networksgraph explorationsingle-agent explorationdeterministic algorithmsKT0 modelKT1 model

0 comments

The pith

Deterministic single-agent exploration in T-interval connected graphs requires window size Omega(m)

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

The paper examines deterministic exploration by one agent that must visit every node in a changing graph sequence where the intersection of any T consecutive graphs remains connected. The agent knows neither the window size T nor the total nodes n or edges m, and works in either of two local visibility models. It proves that T must be linear in m for exploration to succeed in both models, and gives algorithms achieving window sizes within a small multiplicative factor of this bound for wide ranges of m. The same algorithms deliver exploration times that match the established lower bounds up to polylog factors, producing cubic time in n for the weaker visibility model and quadratic time for the stronger one when only n is considered. These results identify the precise connectivity persistence needed for reliable lone-agent traversal in unknown dynamic networks.

Core claim

For both KT0 and KT1 models, a window size T = Omega(m) is necessary for deterministic exploration by a single agent with no knowledge of n, m or T. Deterministic algorithms exist whose required window size is O(ε(n,m)·m + n log² n) with ε(n,m) = ln n / (1 + ln m - ln n); these algorithms also achieve exploration times matching the lower bounds Omega((m-n+1)n) in KT0 and Omega(m) in KT1 up to polylog factors, and become fully tight when m = n^{1+Θ(1)}, yielding Θ(n³) for KT0 and Θ(n²) for KT1 when parameterized solely by n.

What carries the argument

T-interval connectivity (the intersection graph over every window of T steps is connected), together with deterministic traversal procedures that progressively enlarge the working window to compensate for unknown T.

If this is right

When m scales as n to a power greater than 1, both window-size and time bounds become tight without extra logarithmic factors.
Exploration time is Theta(n cubed) in the KT0 model when results are expressed only in terms of n.
Exploration time is Theta(n squared) in the KT1 model when results are expressed only in terms of n.
The algorithms succeed even when the agent has zero advance knowledge of network size, edge count, or window parameter.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

In environments where connectivity persists for far fewer than m steps, reliable exploration may require multiple coordinated agents rather than one.
Allowing limited randomization in the agent's choices could potentially remove the remaining polylogarithmic overheads in time and window size.
Similar lower-bound techniques might be applied to restricted graph families such as planar or bounded-degree dynamic networks to obtain sharper constants.

Load-bearing premise

The encountered graph sequence must be T-interval connected for some unknown fixed T, and the agent must act deterministically with no information about n, m or T.

What would settle it

A deterministic algorithm that explores every possible T-interval-connected sequence using some T = o(m) in the KT1 model without prior knowledge of parameters would disprove the Omega(m) lower bound on window size.

Figures

Figures reproduced from arXiv: 2604.04619 by Junya Nakamura, Koichi Wada, Masahiro Shibata, Naoki Kitamura, S\'ebastien Tixeuil, Toshimitsu Masuzawa, Yuichi Sudo.

**Figure 1.** Figure 1: K5(u, v) (left) and K6(u, v) (right) 3 Lower Bounds In this section, we prove the lower bounds stated in Section 1.3. Specifically, we prove Theorem 3, 4, and 5. To prove Theorem 3, we introduce the graph Kn(u, v) as a gadget, obtained by removing the edge {u, v} from the complete graph on n nodes (see [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗

**Figure 2.** Figure 2: The underlying graph for the proof of Theorem 3, excluding null edges [PITH_FULL_IMAGE:figures/full_fig_p013_2.png] view at source ↗

**Figure 3.** Figure 3: The underlying graph for the proof of Theorem 4, excluding null edges [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗

read the original abstract

We study deterministic exploration by a single agent in $T$-interval-connected graphs, a standard model of dynamic networks in which, for every time window of length $T$, the intersection of the graphs within the window is connected. The agent does not know the window size $T$, nor the number of nodes $n$ or edges $m$, and must visit all nodes of the graph. We consider two visibility models, $KT_0$ and $KT_1$, depending on whether the agent can observe the identifiers of neighboring nodes. We investigate two fundamental questions: the minimum window size that guarantees exploration, and the optimal exploration time under sufficiently large window size. For both models, we show that a window size $T = \Omega(m)$ is necessary. We also present deterministic algorithms whose required window size is $O(\epsilon(n,m)\cdot m + n \log^2 n)$, where $\epsilon(n,m) = \frac{\ln n}{1 + \ln m - \ln n}$. These bounds are tight for a wide range of $m$, in particular when $m = n^{1+\Theta(1)}$. The same algorithms also yield optimal or near-optimal exploration time: we prove lower bounds of $\Omega((m - n + 1)n)$ in the $KT_0$ model and $\Omega(m)$ in the $KT_1$ model, and show that our algorithms match these bounds up to a polylogarithmic factor, while being fully time-optimal when $m = n^{1+\Theta(1)}$. This yields tight bounds when parameterized solely by $n$: $\Theta(n^3)$ for $KT_0$ and $\Theta(n^2)$ for $KT_1$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives useful tight bounds for dense dynamic graphs but the KT0 time lower bound needs an additive term to cover sparse cases like trees.

read the letter

This paper shows that exploration in T-interval-connected dynamic graphs requires a window size T linear in the number of edges m, and supplies deterministic algorithms that come within a small factor of that while also matching time lower bounds up to polylog factors when m is polynomial in n. The results cover both the KT0 model (no neighbor IDs visible) and KT1 (IDs visible), and the algorithms run without prior knowledge of n, m, or T. That combination is the main advance. The necessity proof for T = Ω(m) is clean, and the upper bound on window size O(ε(n,m) m + n log² n) with ε = ln n / (1 + ln m - ln n) is shown to be tight for a wide range of densities, especially the polynomial case that yields the clean Θ(n³) and Θ(n²) time bounds. The algorithms themselves look carefully constructed to handle the unknown parameters and the interval-connectivity guarantee. One soft spot stands out. The KT0 time lower bound is stated as Ω((m - n + 1)n). On a tree where m = n - 1 this expression is zero, yet any correct exploration still needs Ω(n) steps just to visit every node. The bound therefore appears to capture only the extra cost from excess edges and omits the baseline traversal cost; an additive Ω(n) term or a clearer statement for sparse regimes would fix it. The upper bounds do not have this issue, and the parameterized-by-n results remain valid. The rest of the paper reads as standard for this sub-area, with appropriate citations to earlier work on interval connectivity and agent traversal. This is for people who work on mobile agents or dynamic networks in distributed computing. A reader already following that literature will get concrete new limits and algorithms to compare against. It deserves a serious referee because the algorithmic constructions and the necessity arguments for large T are substantive even if one lower-bound expression needs polishing.

Referee Report

1 major / 0 minor

Summary. The paper studies deterministic single-agent exploration of T-interval-connected dynamic graphs in KT0 and KT1 visibility models, where the agent has no knowledge of n, m, or T. It establishes that a window size T = Ω(m) is necessary in both models, provides algorithms requiring T = O(ε(n,m) m + n log² n) with ε(n,m) = ln n / (1 + ln m - ln n), and proves time lower bounds of Ω((m-n+1)n) for KT0 and Ω(m) for KT1, with algorithms matching these up to polylog factors. This yields tight Θ(n³) and Θ(n²) bounds when parameterized only by n.

Significance. If the results hold, they provide tight characterizations of the window size and exploration time for single-agent graph exploration under T-interval connectivity with unknown parameters. The matching upper and lower bounds, particularly the tight results for m = n^{1+Θ(1)} and the parameterized bounds by n, represent a significant advance in understanding the complexity of exploration in dynamic networks. The deterministic algorithms that work without knowledge of n, m, T are noteworthy.

major comments (1)

[Abstract] Abstract: the stated lower bound of Ω((m - n + 1)n) on exploration time in the KT0 model evaluates to Ω(0) for trees (m = n-1). Any correct exploration algorithm requires Ω(n) steps to visit all nodes, so the bound appears to omit an additive Ω(n) term or only charges for the cyclomatic number m-n+1. While the derived Θ(n^3) bound for m=Θ(n^2) remains valid, the general lower-bound statement is imprecise for sparse regimes and is load-bearing for the claimed tightness across all m.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for highlighting this important point regarding the precision of our lower bound statement. We address the comment below.

read point-by-point responses

Referee: [Abstract] Abstract: the stated lower bound of Ω((m - n + 1)n) on exploration time in the KT0 model evaluates to Ω(0) for trees (m = n-1). Any correct exploration algorithm requires Ω(n) steps to visit all nodes, so the bound appears to omit an additive Ω(n) term or only charges for the cyclomatic number m-n+1. While the derived Θ(n^3) bound for m=Θ(n^2) remains valid, the general lower-bound statement is imprecise for sparse regimes and is load-bearing for the claimed tightness across all m.

Authors: We agree with the referee that the lower-bound statement in the abstract (and corresponding theorem) is imprecise for sparse graphs. The term Ω((m-n+1)n) captures the additional cost incurred by the m-n+1 extra edges beyond a spanning tree in the KT0 model; for trees (m=n-1) this term vanishes, yet any correct algorithm still requires Ω(n) time to visit all nodes. Our algorithms achieve O(n log² n) time in this regime, which is optimal up to polylog factors. We will revise the abstract and the statement of the lower bound (Theorem X) to read Ω((m-n+1)n + n) for the KT0 model, making the bound accurate across all m while preserving the tightness claims for m = n^{1+Θ(1)} (where the (m-n+1)n term dominates) and the polylog-factor matching for general m. This change does not affect any other results or proofs. revision: yes

Circularity Check

0 steps flagged

No circularity: independent lower-bound arguments and explicit algorithmic constructions

full rationale

The paper states lower bounds Ω((m-n+1)n) (KT0) and Ω(m) (KT1) on exploration time together with matching algorithmic upper bounds up to polylog factors. These are presented as separate results: the lower bounds are proved via adversarial or information-theoretic arguments on T-interval-connected sequences, while the algorithms are deterministic constructions whose window-size and time guarantees are analyzed directly. Substituting m=Θ(n²) to obtain the n-only bounds Θ(n³) and Θ(n²) is a straightforward algebraic consequence, not a definitional reduction. No self-citation is invoked as a load-bearing uniqueness theorem, no parameter is fitted to data and then relabeled a prediction, and no ansatz is smuggled via prior work. The derivation chain therefore remains self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the domain assumption of T-interval connectivity and standard graph exploration requirements; no free parameters are introduced or fitted, and no new entities are postulated.

axioms (1)

domain assumption Graphs are T-interval-connected for some unknown positive integer T
This is the standard model for the dynamic networks studied, as described in the abstract.

pith-pipeline@v0.9.0 · 5657 in / 1274 out tokens · 75488 ms · 2026-05-10T19:23:22.827723+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

37 extracted references · 37 canonical work pages

[1]

The moore bound for irregular graphs

Noga Alon, Shlomo Hoory, and Nathan Linial. The moore bound for irregular graphs. Graphs and Combinatorics , 18(1):53--57, 2002

work page 2002
[2]

Random walks, universal traversal sequences, and the complexity of maze problems

Romas Aleliunas, Richard M Karp, Richard J Lipton, Laszlo Lovasz, and Charles Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In 20th Annual Symposium on Foundations of Computer Science (sfcs 1979) , pages 218--223. IEEE, 1979

work page 1979
[3]

Dispersion of mobile robots: a study of memory-time trade-offs

John Augustine and William K Moses Jr. Dispersion of mobile robots: a study of memory-time trade-offs. In Proceedings of the 19th International Conference on Distributed Computing and Networking , pages 1--10, 2018

work page 2018
[4]

Want to gather? no need to chatter! SIAM Journal on Computing , 52(2):358--411, 2023

S \'e bastien Bouchard, Yoann Dieudonn \'e , and Andrzej Pelc. Want to gather? no need to chatter! SIAM Journal on Computing , 52(2):358--411, 2023

work page 2023
[5]

Time-varying graphs and dynamic networks

Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems , 27(5):387--408, 2012

work page 2012
[6]

Live exploration of dynamic rings

Giuseppe Antonio Di Luna , Stefan Dobrev, Paola Flocchini, and Nicola Santoro. Live exploration of dynamic rings. In 2016 IEEE 36th International Conference on Distributed Computing Systems (ICDCS) , pages 570--579. IEEE, 2016

work page 2016
[7]

Gathering in dynamic rings

Giuseppe Antonio Di Luna, Paola Flocchini, Linda Pagli, Giuseppe Prencipe, Nicola Santoro, and Giovanni Viglietta. Gathering in dynamic rings. Theoretical Computer Science , 811:79--98, 2020

work page 2020
[8]

Gathering despite mischief

Yoann Dieudonn \'e , Andrzej Pelc, and David Peleg. Gathering despite mischief. ACM Transactions on Algorithms (TALG) , 11(1):1--28, 2014

work page 2014
[9]

On temporal graph exploration

Thomas Erlebach, Michael Hoffmann, and Frank Kammer. On temporal graph exploration. Journal of Computer and System Sciences , 119:1--18, 2021

work page 2021
[10]

On the exploration of time-varying networks

Paola Flocchini, Bernard Mans, and Nicola Santoro. On the exploration of time-varying networks. Theoretical Computer Science , 469:53--68, 2013

work page 2013
[11]

The history of degenerate (bipartite) extremal graph problems

Zolt \'a n F \"u redi and Mikl \'o s Simonovits. The history of degenerate (bipartite) extremal graph problems. In Erd o s centennial , pages 169--264. Springer, 2013

work page 2013
[12]

Exploration of dynamic networks: tight bounds on the number of agents

Tsuyoshi Gotoh, Paola Flocchini, Toshimitsu Masuzawa, and Nicola Santoro. Exploration of dynamic networks: tight bounds on the number of agents. Journal of Computer and System Sciences , 122:1--18, 2021

work page 2021
[13]

Exploration of dynamic tori by multiple agents

Tsuyoshi Gotoh, Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Exploration of dynamic tori by multiple agents. Theoretical Computer Science , 850:202--220, 2021

work page 2021
[14]

Dynamic ring exploration with (H, S) view

Tsuyoshi Gotoh, Yuichi Sudo, Fukuhito Ooshita, and Toshimitsu Masuzawa. Dynamic ring exploration with (H, S) view. Algorithms , 13(6):141, 2020

work page 2020
[15]

Exploration of constantly connected dynamic graphs based on cactuses

David Ilcinkas, Ralf Klasing, and Ahmed Mouhamadou Wade. Exploration of constantly connected dynamic graphs based on cactuses. In International Colloquium on Structural Information and Communication Complexity , pages 250--262. Springer, 2014

work page 2014
[16]

Exploration of the T -interval-connected dynamic graphs: the case of the ring

David Ilcinkas and Ahmed M Wade. Exploration of the T -interval-connected dynamic graphs: the case of the ring. Theory of Computing Systems , 62(5):1144--1160, 2018

work page 2018
[17]

Dispersion is (almost) optimal under (a) synchrony

Ajay D Kshemkalyani, Manish Kumar, Anisur Rahaman Molla, Debasish Pattanayak, and Gokarna Sharma. Dispersion is (almost) optimal under (a) synchrony. In Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures , pages 367--381, 2025

work page 2025
[18]

Distributed computation in dynamic networks

Fabian Kuhn, Nancy Lynch, and Rotem Oshman. Distributed computation in dynamic networks. In Proceedings of the 42nd ACM Symposium on Theory of Computing ( STOC 2010) , pages 513--522. ACM, 2010

work page 2010
[19]

Universal traversal sequences with backtracking

Michal Kouck \`y . Universal traversal sequences with backtracking. Journal of Computer and System Sciences , 65(4):717--726, 2002

work page 2002
[20]

Near-optimal dispersion on arbitrary anonymous graphs

Ajay D Kshemkalyani and Gokarna Sharma. Near-optimal dispersion on arbitrary anonymous graphs. Journal of Computer and System Sciences , page 103656, 2025

work page 2025
[21]

An introduction to temporal graphs: An algorithmic perspective

Othon Michail. An introduction to temporal graphs: An algorithmic perspective. Internet Mathematics , 12(4):239--280, 2016

work page 2016
[22]

Traveling salesman problems in temporal graphs

Othon Michail and Paul G Spirakis. Traveling salesman problems in temporal graphs. Theoretical Computer Science , 634:1--23, 2016

work page 2016
[23]

Quiescence of self-stabilizing gossiping among mobile agents in graphs

Toshimitsu Masuzawa and S \'e bastien Tixeuil. Quiescence of self-stabilizing gossiping among mobile agents in graphs. Theoretical Computer Science , 411(14-15):1567--1582, 2010

work page 2010
[24]

Eulerian walkers as a model of self-organized criticality

Vyatcheslav B Priezzhev, Deepak Dhar, Abhishek Dhar, and Supriya Krishnamurthy. Eulerian walkers as a model of self-organized criticality. Physical Review Letters , 77(25):5079, 1996

work page 1996
[25]

Deterministic rendezvous in networks: A comprehensive survey

Andrzej Pelc. Deterministic rendezvous in networks: A comprehensive survey. Networks , 59(3):331--347, 2012

work page 2012
[26]

Panaite and A

P. Panaite and A. Pelc. Exploring unknown undirected graphs . Journal of Algorithms , 33(2):281--295, 1999

work page 1999
[27]

Deterministic treasure hunt and rendezvous in arbitrary connected graphs

Debasish Pattanayak and Andrzej Pelc. Deterministic treasure hunt and rendezvous in arbitrary connected graphs. Information Processing Letters , 185:106455, 2024

work page 2024
[28]

Reingold

O. Reingold. Undirected connectivity in log-space . Journal of the ACM (JACM) , 55(4):1--24, 2008

work page 2008
[29]

A single agent exploration in unknown undirected graphs with whiteboards

Yuichi Sudo, Daisuke Baba, Junya Nakamura, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. A single agent exploration in unknown undirected graphs with whiteboards. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences , 98(10):2117--2128, 2015

work page 2015
[30]

Partial gathering of mobile agents in dynamic tori

Masahiro Shibata, Naoki Kitamura, Ryota Eguchi, Yuichi Sudo, Junya Nakamura, and Yonghwan Kim. Partial gathering of mobile agents in dynamic tori. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023) , pages 2--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2023

work page 2023
[31]

Move-optimal partial gathering of mobile agents without identifiers or global knowledge in asynchronous unidirectional rings

Masahiro Shibata, Norikazu Kawata, Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Move-optimal partial gathering of mobile agents without identifiers or global knowledge in asynchronous unidirectional rings. Theoretical Computer Science , 822:92--109, 2020

work page 2020
[32]

Self-stabilizing graph exploration by a single agent

Yuichi Sudo, Fukuhito Ooshita, and Sayaka Kamei. Self-stabilizing graph exploration by a single agent. In International Colloquium on Structural Information and Communication Complexity , pages 384--400. Springer, 2025

work page 2025
[33]

Efficient dispersion of mobile agents without global knowledge

Takahiro Shintaku, Yuichi Sudo, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Efficient dispersion of mobile agents without global knowledge. In Stabilization, Safety, and Security of Distributed Systems: 22nd International Symposium, SSS 2020, Austin, TX, USA, November 18--21, 2020, Proceedings 22 , pages 280--294. Springer, 2020

work page 2020
[34]

Near-linear time dispersion of mobile agents

Yuichi Sudo, Masahiro Shibata, Junya Nakamura, Yonghwan Kim, and Toshimitsu Masuzawa. Near-linear time dispersion of mobile agents. In 38th International Symposium on Distributed Computing , 2024

work page 2024
[35]

Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences

Amnon Ta-Shma and Uri Zwick. Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences. ACM Transactions on Algorithms (TALG) , 10(3):1--15, 2014

work page 2014
[36]

Faster treasure hunt and better strongly universal exploration sequences

Qin Xin. Faster treasure hunt and better strongly universal exploration sequences. In International Symposium on Algorithms and Computation , pages 549--560. Springer, 2007

work page 2007
[37]

A distributed ant algorithm for efficiently patrolling a network

Vladimir Yanovski, Israel A Wagner, and Alfred M Bruckstein. A distributed ant algorithm for efficiently patrolling a network. Algorithmica , 37(3):165--186, 2003

work page 2003

[1] [1]

The moore bound for irregular graphs

Noga Alon, Shlomo Hoory, and Nathan Linial. The moore bound for irregular graphs. Graphs and Combinatorics , 18(1):53--57, 2002

work page 2002

[2] [2]

Random walks, universal traversal sequences, and the complexity of maze problems

Romas Aleliunas, Richard M Karp, Richard J Lipton, Laszlo Lovasz, and Charles Rackoff. Random walks, universal traversal sequences, and the complexity of maze problems. In 20th Annual Symposium on Foundations of Computer Science (sfcs 1979) , pages 218--223. IEEE, 1979

work page 1979

[3] [3]

Dispersion of mobile robots: a study of memory-time trade-offs

John Augustine and William K Moses Jr. Dispersion of mobile robots: a study of memory-time trade-offs. In Proceedings of the 19th International Conference on Distributed Computing and Networking , pages 1--10, 2018

work page 2018

[4] [4]

Want to gather? no need to chatter! SIAM Journal on Computing , 52(2):358--411, 2023

S \'e bastien Bouchard, Yoann Dieudonn \'e , and Andrzej Pelc. Want to gather? no need to chatter! SIAM Journal on Computing , 52(2):358--411, 2023

work page 2023

[5] [5]

Time-varying graphs and dynamic networks

Arnaud Casteigts, Paola Flocchini, Walter Quattrociocchi, and Nicola Santoro. Time-varying graphs and dynamic networks. International Journal of Parallel, Emergent and Distributed Systems , 27(5):387--408, 2012

work page 2012

[6] [6]

Live exploration of dynamic rings

Giuseppe Antonio Di Luna , Stefan Dobrev, Paola Flocchini, and Nicola Santoro. Live exploration of dynamic rings. In 2016 IEEE 36th International Conference on Distributed Computing Systems (ICDCS) , pages 570--579. IEEE, 2016

work page 2016

[7] [7]

Gathering in dynamic rings

Giuseppe Antonio Di Luna, Paola Flocchini, Linda Pagli, Giuseppe Prencipe, Nicola Santoro, and Giovanni Viglietta. Gathering in dynamic rings. Theoretical Computer Science , 811:79--98, 2020

work page 2020

[8] [8]

Gathering despite mischief

Yoann Dieudonn \'e , Andrzej Pelc, and David Peleg. Gathering despite mischief. ACM Transactions on Algorithms (TALG) , 11(1):1--28, 2014

work page 2014

[9] [9]

On temporal graph exploration

Thomas Erlebach, Michael Hoffmann, and Frank Kammer. On temporal graph exploration. Journal of Computer and System Sciences , 119:1--18, 2021

work page 2021

[10] [10]

On the exploration of time-varying networks

Paola Flocchini, Bernard Mans, and Nicola Santoro. On the exploration of time-varying networks. Theoretical Computer Science , 469:53--68, 2013

work page 2013

[11] [11]

The history of degenerate (bipartite) extremal graph problems

Zolt \'a n F \"u redi and Mikl \'o s Simonovits. The history of degenerate (bipartite) extremal graph problems. In Erd o s centennial , pages 169--264. Springer, 2013

work page 2013

[12] [12]

Exploration of dynamic networks: tight bounds on the number of agents

Tsuyoshi Gotoh, Paola Flocchini, Toshimitsu Masuzawa, and Nicola Santoro. Exploration of dynamic networks: tight bounds on the number of agents. Journal of Computer and System Sciences , 122:1--18, 2021

work page 2021

[13] [13]

Exploration of dynamic tori by multiple agents

Tsuyoshi Gotoh, Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Exploration of dynamic tori by multiple agents. Theoretical Computer Science , 850:202--220, 2021

work page 2021

[14] [14]

Dynamic ring exploration with (H, S) view

Tsuyoshi Gotoh, Yuichi Sudo, Fukuhito Ooshita, and Toshimitsu Masuzawa. Dynamic ring exploration with (H, S) view. Algorithms , 13(6):141, 2020

work page 2020

[15] [15]

Exploration of constantly connected dynamic graphs based on cactuses

David Ilcinkas, Ralf Klasing, and Ahmed Mouhamadou Wade. Exploration of constantly connected dynamic graphs based on cactuses. In International Colloquium on Structural Information and Communication Complexity , pages 250--262. Springer, 2014

work page 2014

[16] [16]

Exploration of the T -interval-connected dynamic graphs: the case of the ring

David Ilcinkas and Ahmed M Wade. Exploration of the T -interval-connected dynamic graphs: the case of the ring. Theory of Computing Systems , 62(5):1144--1160, 2018

work page 2018

[17] [17]

Dispersion is (almost) optimal under (a) synchrony

Ajay D Kshemkalyani, Manish Kumar, Anisur Rahaman Molla, Debasish Pattanayak, and Gokarna Sharma. Dispersion is (almost) optimal under (a) synchrony. In Proceedings of the 37th ACM Symposium on Parallelism in Algorithms and Architectures , pages 367--381, 2025

work page 2025

[18] [18]

Distributed computation in dynamic networks

Fabian Kuhn, Nancy Lynch, and Rotem Oshman. Distributed computation in dynamic networks. In Proceedings of the 42nd ACM Symposium on Theory of Computing ( STOC 2010) , pages 513--522. ACM, 2010

work page 2010

[19] [19]

Universal traversal sequences with backtracking

Michal Kouck \`y . Universal traversal sequences with backtracking. Journal of Computer and System Sciences , 65(4):717--726, 2002

work page 2002

[20] [20]

Near-optimal dispersion on arbitrary anonymous graphs

Ajay D Kshemkalyani and Gokarna Sharma. Near-optimal dispersion on arbitrary anonymous graphs. Journal of Computer and System Sciences , page 103656, 2025

work page 2025

[21] [21]

An introduction to temporal graphs: An algorithmic perspective

Othon Michail. An introduction to temporal graphs: An algorithmic perspective. Internet Mathematics , 12(4):239--280, 2016

work page 2016

[22] [22]

Traveling salesman problems in temporal graphs

Othon Michail and Paul G Spirakis. Traveling salesman problems in temporal graphs. Theoretical Computer Science , 634:1--23, 2016

work page 2016

[23] [23]

Quiescence of self-stabilizing gossiping among mobile agents in graphs

Toshimitsu Masuzawa and S \'e bastien Tixeuil. Quiescence of self-stabilizing gossiping among mobile agents in graphs. Theoretical Computer Science , 411(14-15):1567--1582, 2010

work page 2010

[24] [24]

Eulerian walkers as a model of self-organized criticality

Vyatcheslav B Priezzhev, Deepak Dhar, Abhishek Dhar, and Supriya Krishnamurthy. Eulerian walkers as a model of self-organized criticality. Physical Review Letters , 77(25):5079, 1996

work page 1996

[25] [25]

Deterministic rendezvous in networks: A comprehensive survey

Andrzej Pelc. Deterministic rendezvous in networks: A comprehensive survey. Networks , 59(3):331--347, 2012

work page 2012

[26] [26]

Panaite and A

P. Panaite and A. Pelc. Exploring unknown undirected graphs . Journal of Algorithms , 33(2):281--295, 1999

work page 1999

[27] [27]

Deterministic treasure hunt and rendezvous in arbitrary connected graphs

Debasish Pattanayak and Andrzej Pelc. Deterministic treasure hunt and rendezvous in arbitrary connected graphs. Information Processing Letters , 185:106455, 2024

work page 2024

[28] [28]

Reingold

O. Reingold. Undirected connectivity in log-space . Journal of the ACM (JACM) , 55(4):1--24, 2008

work page 2008

[29] [29]

A single agent exploration in unknown undirected graphs with whiteboards

Yuichi Sudo, Daisuke Baba, Junya Nakamura, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. A single agent exploration in unknown undirected graphs with whiteboards. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences , 98(10):2117--2128, 2015

work page 2015

[30] [30]

Partial gathering of mobile agents in dynamic tori

Masahiro Shibata, Naoki Kitamura, Ryota Eguchi, Yuichi Sudo, Junya Nakamura, and Yonghwan Kim. Partial gathering of mobile agents in dynamic tori. In 2nd Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2023) , pages 2--1. Schloss Dagstuhl--Leibniz-Zentrum f \"u r Informatik, 2023

work page 2023

[31] [31]

Move-optimal partial gathering of mobile agents without identifiers or global knowledge in asynchronous unidirectional rings

Masahiro Shibata, Norikazu Kawata, Yuichi Sudo, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Move-optimal partial gathering of mobile agents without identifiers or global knowledge in asynchronous unidirectional rings. Theoretical Computer Science , 822:92--109, 2020

work page 2020

[32] [32]

Self-stabilizing graph exploration by a single agent

Yuichi Sudo, Fukuhito Ooshita, and Sayaka Kamei. Self-stabilizing graph exploration by a single agent. In International Colloquium on Structural Information and Communication Complexity , pages 384--400. Springer, 2025

work page 2025

[33] [33]

Efficient dispersion of mobile agents without global knowledge

Takahiro Shintaku, Yuichi Sudo, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Efficient dispersion of mobile agents without global knowledge. In Stabilization, Safety, and Security of Distributed Systems: 22nd International Symposium, SSS 2020, Austin, TX, USA, November 18--21, 2020, Proceedings 22 , pages 280--294. Springer, 2020

work page 2020

[34] [34]

Near-linear time dispersion of mobile agents

Yuichi Sudo, Masahiro Shibata, Junya Nakamura, Yonghwan Kim, and Toshimitsu Masuzawa. Near-linear time dispersion of mobile agents. In 38th International Symposium on Distributed Computing , 2024

work page 2024

[35] [35]

Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences

Amnon Ta-Shma and Uri Zwick. Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences. ACM Transactions on Algorithms (TALG) , 10(3):1--15, 2014

work page 2014

[36] [36]

Faster treasure hunt and better strongly universal exploration sequences

Qin Xin. Faster treasure hunt and better strongly universal exploration sequences. In International Symposium on Algorithms and Computation , pages 549--560. Springer, 2007

work page 2007

[37] [37]

A distributed ant algorithm for efficiently patrolling a network

Vladimir Yanovski, Israel A Wagner, and Alfred M Bruckstein. A distributed ant algorithm for efficiently patrolling a network. Algorithmica , 37(3):165--186, 2003

work page 2003