Recolorable Graph Exploration by an Oblivious Agent with Fewer Colors

Haruki Kanaya; Ryota Eguchi; Shoma Hiraoka; Shota Takahashi; Yuichi Sudo

REVIEW 2 major objections 4 minor 1 cited by

Recolorable Graph Exploration by an Oblivious Agent with Fewer Colors

T0 review · 2 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

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

Pith's one-line read A six-color rule function lets a memoryless agent explore every connected graph, improving the known bound of eight.

desk verdict A real six-color improvement over the eight-color bound, with thoughtful disclosure of a model ambiguity; the proofs hold up and it deserves peer review. read the letter →

arxiv 2505.02789 v1 pith:IRT2M2RN submitted 2025-05-05 cs.DC

Shota Takahashi , Haruki Kanaya , Shoma Hiraoka , Ryota Eguchi , Yuichi Sudo This is my paper · ORCID

classification cs.DC MSC 68W1505C8568R10

keywords graphexplorationobliviousagentnodecoloringrecolorablemodelcolorcomplexitysemi-DFSphi-freegraphsmobileagents

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

The paper establishes that in the recolorable model of graph exploration—where an oblivious agent may repaint its current node, sees neighbor colors, and moves to an adversarially chosen neighbor of a stated target color—six colors are sufficient to explore every connected undirected graph. This improves the eight-color bound previously known. The agent simulates a chord-free variant of depth-first search (semi-DFS), using the six colors to encode the return path, finished nodes, untouched nodes, and temporary scan states. The same technique gives five colors on triangle-free graphs, and a separate DAG-based algorithm gives five colors on φ-free graphs, a class that includes all graphs of maximum degree three and all cacti.

What carries the argument

The central object for the arbitrary-graph result is semi-DFS, a depth-first search modified so that the maintained return path $P$ is always chordless: the path is extended only to a neighbor $u$ of the head with $u \notin F \cup P \cup \bigcup_{i<k} N(u_i)$, a condition encoded by the set $U(P,F)$. This chordlessness is what allows six colors to encode enough information to backtrack without port labels. The φ-free result rests on a different mechanism: three distance colors $d_0,d_1,d_2$ orient a directed acyclic graph by pointing from $d_i$ to $d_{i+1}$ modulo 3, and the rule $f(M) = \min\{ i \in \{0,1,2\} : d_{i-1} \in M \wedge d_{i+1} \notin M \}$ assigns a node the unique color that preserves acyclicity; Lemma 2's characterization of φ-free graphs ensures Rule 1 can safely finish a node only when its degree is exactly three.

What would settle it

A concrete way to test the claim is to implement the rule function AGen6 and run it on every connected graph up to some fixed size with all adversarial choices among tied neighbor colors; Theorem 1 predicts every maximal execution terminates with all nodes colored fin, so any single execution that terminates with an init- or path-colored node remaining would refute it.

Watch

Extended reading notes

Core claim

The central discovery is a six-color rule function, AGen6, that lets a memoryless agent explore arbitrary graphs by simulating semi-DFS. In this simulation, nodes colored path together with the head-colored node head1 encode the current return path, nodes colored fin are finished, and nodes colored init have not been visited; the two remaining colors, head2 and neigh, drive a probe-and-reset check of the head's neighbors. An init-colored neighbor is appended to the path only if it is not already finished, not on the path, and not adjacent to any earlier path node; otherwise it is temporarily marked neigh and then reset. When no candidate remains, the head is colored fin and the agent backtracks along the path-colored predecessor. The proof shows that from every regular configuration the agent simulates exactly one iteration of the semi-DFS loop, so when the semi-DFS terminates all nodes are colored fin and the agent stops at the starting node.

Load-bearing premise

The six-color result depends on allowing a node to be recolored from any other color back to the initial color, an interpretation the authors flag as ambiguous in the original model; under the opposite interpretation their arbitrary-graph algorithm needs seven colors and their triangle-free algorithm needs six.

Editorial extensions

If this is right

Six colors replace eight for exploring arbitrary connected graphs in the recolorable model, and five colors replace six on triangle-free graphs.
Five colors suffice for every φ-free graph, which includes all graphs of maximum degree three and every cactus.
The color count is sensitive to a model ambiguity: if recoloring a node back to the initial color is forbidden, the arbitrary-graph bound becomes seven and the triangle-free bound becomes six, while the φ-free bound remains five.
The paper gives no nontrivial lower bound, so the question of whether fewer than six colors can explore arbitrary graphs remains open.
The stay option is shown not to extend the model, so the six-color algorithm fits the original rule-function model exactly.

Reading between the lines

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

The local characterization of φ-free graphs (a degree-4+ vertex has at most two neighbors in any component of $G-v$) gives a cheap way to recognize candidate graphs for the five-color algorithm; graphs violating it are the natural place to look for a six-color lower bound.
The semi-DFS construction suggests a design pattern: any traversal whose maintained state is an induced path can likely be simulated in this recoloring model with a constant palette, though the paper neither states nor proves such a generalization.
A one-bit agent memory would likely lower the color count further; the authors raise the idea as future work, and nothing in the six-color encoding suggests it is tight.

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

Private take: this is a genuine improvement in a niche model, and the proofs are in good shape. The six-color arbitrary-graph algorithm is the headline result. Its semi-DFS idea—keeping the search path chord-free so a constant-color scheme can backtrack reliably—is a real technique, not a tweaked version of the earlier eight-color BFS. The two head colors do the work of disambiguating return moves when triangles exist; the triangle-free variant merges them, and the phi-free five-color algorithm is a separate construction using a distance-color DAG. The paper is constructive throughout: explicit rule tables, no hidden fitting, and the claims are what they appear to be.

What I liked: the authors are straight about the one modeling ambiguity that matters. Whether a non-initial node may be recolored back to the initial color is genuinely under-specified in the original model, and they state their interpretation, give the textual evidence, and quantify the cost if the opposite reading is right (seven/six colors instead of six/five, with the phi-free result unaffected). That is the right way to handle a fuzzy baseline. The semi-DFS correctness proof is careful; I checked the expansion and backtracking cases and they hold.

Soft spots, in proportion. The final step of Theorem 3 compresses an invariant into one line: 'Lemma 5 ... implies F=V' does not follow from connectedness alone. The missing step is that APF5 never outputs init as a new color, so no fin node ever has an init-colored neighbor; connectedness then forces F=V. The invariant is valid, so this is a presentation gap, not an error. Also, the phi-free class is defined exactly to make the five-color approach work; it does include max-degree-3 graphs and cacti, so it is a natural enough restriction, but it is tailored. No non-trivial lower bound is given; the authors admit this. That is fine—it is not promised.

Who gains: researchers working on mobile-agent exploration with weak agents, and anyone interested in what constant-color zero-memory agents can do. The paper will be read by a small community, but it deserves a serious referee, and I would accept it. Recommended: send it to review, with a request that the authors expand the Theorem 3 invariant step.

Referee Report

2 major / 4 minor

Summary. The paper studies the recolorable node-coloring model for exploration by an oblivious agent introduced by Böckenhauer et al. [3], in which the agent observes the colors of its current node and neighbors, recolors the current node, and moves to a neighbor of a specified target color. The main results are: (1) an algorithm AGen6 using six colors (including the initial color) that explores every connected graph; (2) a five-color variant for triangle-free graphs; and (3) a five-color algorithm APF5 for φ-free graphs, a class containing all graphs of maximum degree 3 and all cacti. The six-color algorithm is based on a 'semi-DFS' traversal that avoids chords in the maintained return path, with two head colors used to make backtracking robust. The φ-free algorithm maintains a mod-3 distance coloring and shows that the two-color-per-distance-class redundancy of the earlier BFS approach can be collapsed for φ-free graphs. Section 5 discusses an ambiguity in [3] concerning whether a node may be recolored back to the initial color.

Significance. If the results are correct and the model comparison with [3] is legitimate, the paper improves the known upper bound for arbitrary graphs to six colors in the paper's counting convention, and the φ-free analysis is a clean structural contribution (Lemma 2 is a useful characterization). The rule tables are explicit and the algorithms are constructive, so the proofs can be verified independently. The paper also honestly quantifies the effect of the initial-color-recoloring ambiguity. However, the equivalence claim for the stay action needs scrutiny, and the final step of Theorem 3 contains a compressed inference that must be repaired, so the contribution is not yet fully rigorous in its present form.

major comments (2)

[Section 2 (footnote)] The footnote in Section 2 claims that adding the stay option 'does not change or extend the model,' with the justification that one can set ξ(c,M)=ξ(x,M) whenever ξ(c,M)=(x,stay). This is circular: to apply ξ(x,M), the agent would have to remain at the same node for another step, which is exactly the capability being introduced. In the stay-free original model of [3], every non-stop step moves the agent to a neighbor, so the recursive definition does not simulate staying. The stay action is used in essential places in all the algorithms (e.g., AGen6 Rules 3, 5, and 10; APF5 Rules 2 and 3), not merely as a notational convenience. Consequently, Theorems 1–3 are established for a model that may be strictly more expressive than the model of [3], and the claimed comparison with the eight-color bound is not justified. The authors should either give a rigorous simulation of stay in the stay-free model or explicitly state that the results are for the extended model and discuss what this means for the comparison with [3].
[Theorem 3 (final paragraph)] In the final configuration argument, the sentence 'Therefore, all nodes must be colored fin' does not follow from the two preceding observations: 'no neighbor of s is init' and 'no node retains a distance color' still allow an init-colored node that is not adjacent to s. The missing step is an invariant stating that once a node becomes fin, it never has an init-colored neighbor; this prevents any edge from F to an init node in the final configuration, and connectedness then forces F=V. The invariant is true (Rule 4 is applied only at distance-colored nodes and moves to an init neighbor, so a node colored fin cannot have such a neighbor at that moment, and no node ever changes back to init), but it must be stated and proved. Without this step, Lemma 5 alone does not imply F=V.

minor comments (4)

[Abstract / Section 1] Because the paper changes the color-counting convention relative to [3], the abstract should state explicitly that the six colors include the initial color and correspond to five colors in [3]'s convention. As written, a reader may misread the 'eight-color bound' as a comparison in a single convention.
[Lemma 5] The final step 'Thus, G[V\F(i)]−v must be connected' is too compressed. The reader must supply the argument that a directed path in D from s to a neighbor of v is also an undirected path in G[V\F(i)]−v, so every component adjacent to v remains attached to s. Please expand this inference.
[Lemma 4] The sentence 'before this first visit, the agent can have visited at most two neighbors of v' needs justification. The intended argument is that any segment of the agent's walk between two visited neighbors of v, while v has not been visited, lies in G−v and hence places those neighbors in the same connected component of G−v; if three such neighbors had been visited, Lemma 2 would be contradicted. Please state this argument explicitly.
[Appendix (Theorem 2)] The proof of Theorem 2 is considerably terser than the proof of Theorem 1. Several steps, such as the use of Rule 9 followed by Rule 12 to move to the path predecessor and then return to the head, are described only in prose. A short invariant or a state-diagram comparable to Figure 1 would make this proof much easier to verify.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the six-color and five-color algorithms are constructive simulations of independent graph-search procedures, and the disclosed model ambiguity is a rule-of-the-game assumption, not a fitted input or imported conclusion.

full rationale

The central derivation chain is self-contained. Theorem 1 proves correctness of AGen6 by maintaining a regular-configuration invariant that explicitly tracks the path P and finished set F of the semi-DFS procedure (Algorithm 1). The invariant is a designed correspondence between colors and the search state, not a conclusion assumed by construction; the decisive Lemma 1 (semi-DFS eventually terminates with F=V) is proved independently from the definition of U(P,F), with no reference to the color algorithm. All algorithm rules are given explicitly and use no fitted parameters, and no quantity called a 'prediction' is derived from previously fitted data. The prior work [3] is used only as the model baseline and the eight-color benchmark; the correctness arguments for the new algorithms do not import any unverified claim from [3]. Author self-citations ([18]-[20]) appear only in the introductory survey of related problems and are not load-bearing. The model ambiguity discussed in Section 5 is explicitly disclosed: the assumption that a node may be recolored from a non-initial color back to the initial color is a rule-of-the-game interpretation, and the authors quantify exactly how the stated color bounds would change under the opposite interpretation (seven colors for arbitrary graphs, six for triangle-free, five unchanged for phi-free graphs). This is a transparent modeling assumption, not circular reasoning. One presentation gap exists in Theorem 3, where the sentence 'By Lemma 5 ... implies F=V' needs the additional invariant, proved just before, that no node retains a distance color in the final configuration and that the starting node s is colored fin upon termination; that invariant is valid and supplies the missing step, so the gap is expository only and does not create circularity.

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

The central claims depend on no fitted numerical parameters. The load-bearing assumptions are the modeling choices inherited from the original paper plus the explicitly discussed permission to recolor back to the initial color. No new physical or mathematical entities are postulated.

assumptions (3)

domain assumption A node may be recolored from a non-initial color back to the initial color.
Section 1 and Section 5: the paper assumes this interpretation of the original model. If disallowed, the six-color and five-color triangle-free claims degrade by one color each.
domain assumption Graphs are simple, undirected, and connected.
Section 2: stated at the start of the preliminaries and inherited from the original model.
domain assumption The agent is oblivious and has no port numbers; ties among same-colored neighbors are resolved adversarially.
Section 2: this is the defining feature of the model introduced by Böckenhauer et al. [3] and is used throughout the correctness proofs.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Recolorable Graph Exploration by an Oblivious Agent with Fewer Colors." pith.science (2026). https://pith.science/paper/IRT2M2RN

@misc{pith2026250502789,
  author       = {Pith},
  title        = {Pith review of: Recolorable Graph Exploration by an Oblivious Agent with Fewer Colors},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/IRT2M2RN}},
  note         = {Machine review of arXiv:2505.02789}
}

abstract

Recently, B\"ockenhauer, Frei, Unger, and Wehner (SIROCCO 2023) introduced a novel variant of the graph exploration problem in which a single memoryless agent must visit all nodes of an unknown, undirected, and connected graph before returning to its starting node. Unlike the standard model for mobile agents, edges are not labeled with port numbers. Instead, the agent can color its current node and observe the color of each neighboring node. To move, it specifies a target color and then moves to an adversarially chosen neighbor of that color. B\"ockenhauer~et al.~analyzed the minimum number of colors required for successful exploration and proposed an elegant algorithm that enables the agent to explore an arbitrary graph using only eight colors. In this paper, we present a novel graph exploration algorithm that requires only six colors. Furthermore, we prove that five colors are sufficient if we consider only a restricted class of graphs, which we call the $\varphi$-free graphs, a class that includes every graph with maximum degree at most three and every cactus.

Figures

Figures reproduced from arXiv: 2505.02789 by the authors.

**Figure 1.** Lifecycle of node colors in algorithm AGen6 Full Visitation: Let X ⊆ V be the set F upon termination. Assume, for the sake of contradiction, that X ⊂ V . Since G is connected, the boundary set B(X) = {v ∈ X | ∃u ∈ V \ X : {u, v} ∈ E} is not empty. Let vin be the node in B(X) that was removed from the return path P most recently, and choose any vout ∈ N(vin)\X ̸= ∅. Suppose the return path was P = (u1, u2, . . . , uk… view at source ↗

**Figure 3.** Removal of the head Algorithm AGen6 simulates the Semi-DFS specified by Algorithm 1. In AGen6, nodes colored fin represent finished nodes (i.e., the nodes in F), while nodes colored path and head1 form the path P of the semi-DFS. Nodes colored init indicate that they are neither finished nor on P. The colors head2 and neigh are employed to find a node in U(P, F) = N(uk) \ (F ∪ {u1, u2, . . . , uk} ∪ Sk−1 i=1 N(ui)).… view at source ↗

**Figure 5.** φ-shaped graph in the proof of Lemma 2 • {t, u} ∈ E, A graph is said to be φ-free if it does not contain any φ-shaped subgraph. Typical examples of φ-shaped graphs are shown in [PITH_FULL_IMAGE:figures/full_fig_p008_5.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Treasure Hunt in Anonymous Graphs with Quantum Pebbles by Oblivious Agents
quant-ph 2025-09 conditional novelty 3.0 of 10

A quantum pebble that emits repeated copies of a port-encoding qubit lets an oblivious agent walk to a treasure in D steps using D pebbles.

Reference graph

Works this paper leans on

20 extracted references · 19 canonical work pages · cited by 1 Pith paper

[3]

Zero-memory graph exploration with unknown inports

Hans-Joachim Böckenhauer, Fabian Frei, Walter Unger, and David Wehner. Zero-memory graph exploration with unknown inports. InInternational Colloquium on Structural Information and Communication Complexity, pages 246–261. Springer, 2023

work page 2023
[1]

Moses Jr

John Augustine and William K. Moses Jr. Dispersion of mobile robots.Proceedings of the 19th International Conference on Distributed Computing and Networking, Jan 2018

work page 2018
[2]

Zero-memory graph exploration with unknown inports, 2023

Hans-Joachim Böckenhauer, Fabian Frei, Walter Unger, and David Wehner. Zero-memory graph exploration with unknown inports, 2023

work page 2023
[4]

Kowalski, and Dominik Pająk

Dominik Bojko, Karol Gotfryd, Dariusz R. Kowalski, and Dominik Pająk. Tree Exploration in Dual-Memory Model. In47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), pages 22:1–22:16, 2022

work page 2022
[5]

Searching for a black hole in arbitrary networks: Optimal mobile agents protocols.Distributed Computing, 19:1–99999, 2006

Stefan Dobrev, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Searching for a black hole in arbitrary networks: Optimal mobile agents protocols.Distributed Computing, 19:1–99999, 2006

work page 2006
[6]

Mobile search for a black hole in an anonymous ring.Algorithmica, 48:67–90, 2007

Stefan Dobrev, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Mobile search for a black hole in an anonymous ring.Algorithmica, 48:67–90, 2007

work page 2007
[7]

Using scattered mobile agents to locate a black hole in an un-oriented ring with tokens.International Journal of Foundations of Computer Science, 19(06):1355–1372, 2008

Stefan Dobrev, Nicola Santoro, and Wei Shi. Using scattered mobile agents to locate a black hole in an un-oriented ring with tokens.International Journal of Foundations of Computer Science, 19(06):1355–1372, 2008

work page 2008
[8]

Efficient dispersion of mobile robots on graphs

Ajay D Kshemkalyani and Faizan Ali. Efficient dispersion of mobile robots on graphs. InProceedings of the 20th International Conference on Distributed Computing and Networking, pages 218–227, 2019

work page 2019

Show all 20 references

[9]

Efficient dispersion of mobile robots on arbitrary graphs and grids.arXiv preprint arXiv:1812.05352, 2018

Ajay D Kshemkalyani, Anisur Rahaman Molla, and Gokarna Sharma. Efficient dispersion of mobile robots on arbitrary graphs and grids.arXiv preprint arXiv:1812.05352, 2018

2018 arXiv
[10]

Fast dispersion of mobile robots on arbitrary graphs

Ajay D Kshemkalyani, Anisur Rahaman Molla, and Gokarna Sharma. Fast dispersion of mobile robots on arbitrary graphs. InInternational Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, pages 23–40. Springer, 2019

2019
[11]

Randomized gathering of mobile agents in anonymous unidirectional ring networks.IEEE Transactions on Par- allel and Distributed Systems, 25(5):1289–1296, 2013

Fukuhito Ooshita, Shinji Kawai, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Randomized gathering of mobile agents in anonymous unidirectional ring networks.IEEE Transactions on Par- allel and Distributed Systems, 25(5):1289–1296, 2013

2013
[12]

Panaite and A

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

1999
[13]

Eulerian walkers as a model of self-organized criticality.Physical Review Letters, 77(25):5079, 1996

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

1996
[14]

Reingold

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

2008
[15]

Uniform deployment of mobile agents in asynchronous rings

Masahiro Shibata, Toshiya Mega, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Ma- suzawa. Uniform deployment of mobile agents in asynchronous rings. InProceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pages 415–424, 2016

2016
[16]

Partial gathering of mobile agents in arbitrary networks.IEICE TRANSACTIONS on Information and Systems, 102(3):444–453, 2019

Masahiro Shibata, Daisuke Nakamura, Fukuhito Ooshita, Hirotsugu Kakugawa, and Toshimitsu Masuzawa. Partial gathering of mobile agents in arbitrary networks.IEICE TRANSACTIONS on Information and Systems, 102(3):444–453, 2019. 12

2019
[17]

Uniform deployment of mobile agents in dynamic rings

Masahiro Shibata, Yuichi Sudo, Junya Nakamura, and Yonghwan Kim. Uniform deployment of mobile agents in dynamic rings. InInternational Symposium on Stabilizing, Safety, and Security of Distributed Systems, pages 248–263. Springer, 2020

2020
[18]

A single agent exploration in unknown undirected graphs with whiteboards

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

2015
[19]

Self-stabilizing graph exploration by a sin- gle agent

Yuichi Sudo, Fukuhito Ooshita, and Sayaka Kamei. Self-stabilizing graph exploration by a sin- gle agent. InThe 32nd International Colloquium On Structural Information and Communication Complexity (SIROCCO 2025), to appear, 2020

2025
[20]

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. In38th International Symposium on Distributed Com- puting (DISC 2024), pages 38:1–38:22, 2024. 13 Algorithm4:GraphExplorationAlgorithmForTriangl...

2024

Pith tools

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

[1] [3]

Zero-memory graph exploration with unknown inports

Hans-Joachim Böckenhauer, Fabian Frei, Walter Unger, and David Wehner. Zero-memory graph exploration with unknown inports. InInternational Colloquium on Structural Information and Communication Complexity, pages 246–261. Springer, 2023

work page 2023

[2] [1]

Moses Jr

John Augustine and William K. Moses Jr. Dispersion of mobile robots.Proceedings of the 19th International Conference on Distributed Computing and Networking, Jan 2018

work page 2018

[3] [2]

Zero-memory graph exploration with unknown inports, 2023

Hans-Joachim Böckenhauer, Fabian Frei, Walter Unger, and David Wehner. Zero-memory graph exploration with unknown inports, 2023

work page 2023

[4] [4]

Kowalski, and Dominik Pająk

Dominik Bojko, Karol Gotfryd, Dariusz R. Kowalski, and Dominik Pająk. Tree Exploration in Dual-Memory Model. In47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), pages 22:1–22:16, 2022

work page 2022

[5] [5]

Searching for a black hole in arbitrary networks: Optimal mobile agents protocols.Distributed Computing, 19:1–99999, 2006

Stefan Dobrev, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Searching for a black hole in arbitrary networks: Optimal mobile agents protocols.Distributed Computing, 19:1–99999, 2006

work page 2006

[6] [6]

Mobile search for a black hole in an anonymous ring.Algorithmica, 48:67–90, 2007

Stefan Dobrev, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Mobile search for a black hole in an anonymous ring.Algorithmica, 48:67–90, 2007

work page 2007

[7] [7]

Using scattered mobile agents to locate a black hole in an un-oriented ring with tokens.International Journal of Foundations of Computer Science, 19(06):1355–1372, 2008

Stefan Dobrev, Nicola Santoro, and Wei Shi. Using scattered mobile agents to locate a black hole in an un-oriented ring with tokens.International Journal of Foundations of Computer Science, 19(06):1355–1372, 2008

work page 2008

[8] [8]

Efficient dispersion of mobile robots on graphs

Ajay D Kshemkalyani and Faizan Ali. Efficient dispersion of mobile robots on graphs. InProceedings of the 20th International Conference on Distributed Computing and Networking, pages 218–227, 2019

work page 2019