Graph exploration by a finite automaton
From MaRDI portal
Publication:2575752
DOI10.1016/j.tcs.2005.07.014zbMath1081.68045OpenAlexW2039936247MaRDI QIDQ2575752
Pierre Fraigniaud, David Ilcinkas, David Peleg, Guy Peer, Andrzej Pelc
Publication date: 6 December 2005
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2005.07.014
Related Items (52)
Optimal dispersion on an anonymous ring in the presence of weak Byzantine robots ⋮ A probabilistic model for the interaction of an agent with a network environment ⋮ An improved lower bound for competitive graph exploration ⋮ TIME OPTIMAL ALGORITHMS FOR BLACK HOLE SEARCH IN RINGS ⋮ Memory Efficient Anonymous Graph Exploration ⋮ Graph Decomposition for Improving Memoryless Periodic Exploration ⋮ Collaborative Exploration by Energy-Constrained Mobile Robots ⋮ Lower and upper competitive bounds for online directed graph exploration ⋮ Collision-free network exploration ⋮ Homomorphisms on graph-walking automata ⋮ Exploring a dynamic ring without landmark ⋮ Distributed exploration of dynamic rings ⋮ The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks ⋮ Robustness of the rotor-router mechanism ⋮ Exploration of Time-Varying Connected Graphs with Silent Agents ⋮ Homomorphisms and inverse homomorphisms on graph-walking automata ⋮ Efficient live exploration of a dynamic ring with mobile robots ⋮ How many ants does it take to find the food? ⋮ Exploring an unknown dangerous graph with a constant number of tokens ⋮ Invited paper: One bit agent memory is enough for snap-stabilizing perpetual exploration of cactus graphs with distinguishable cycles ⋮ On the Power of Local Orientations ⋮ State complexity of transforming graph-walking automata to halting, returning and reversible ⋮ Fault-tolerant dispersion of mobile robots ⋮ Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs ⋮ Ping pong in dangerous graphs: optimal black hole search with pebbles ⋮ Graph decomposition for memoryless periodic exploration ⋮ A time to cast away stones ⋮ On defining linear orders by automata ⋮ Reversibility of computations in graph-walking automata ⋮ Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens ⋮ Building a nest by an automaton ⋮ Distributed chasing of network intruders ⋮ Fast periodic graph exploration with constant memory ⋮ Derandomizing random walks in undirected graphs using locally fair exploration strategies ⋮ Exploration of dynamic networks: tight bounds on the number of agents ⋮ Shape recognition by a finite automaton robot ⋮ LABEL-GUIDED GRAPH EXPLORATION WITH ADJUSTABLE RATIO OF LABELS ⋮ Unnamed Item ⋮ Anonymous graph exploration without collision by mobile robots ⋮ Collaborative exploration of trees by energy-constrained mobile robots ⋮ Wireless evacuation on \(m\) rays with \(k\) searchers ⋮ A general lower bound for collaborative tree exploration ⋮ Connected reconfiguration of lattice-based cellular structures by finite-memory robots ⋮ Exploration of High-Dimensional Grids by Finite Automata ⋮ More Efficient Periodic Traversal in Anonymous Undirected Graphs ⋮ Black Hole Search in Directed Graphs ⋮ An Improved Strategy for Exploring a Grid Polygon ⋮ State complexity of union and intersection on graph-walking automata ⋮ Dispersion of mobile robots on directed anonymous graphs ⋮ Chaotic Traversal (CHAT): Very Large Graphs Traversal Using Chaotic Dynamics ⋮ Distributed graph searching with a sense of direction ⋮ Two-agent tree evacuation
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Universal sequences for complete graphs
- Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques
- Automaten in planaren Graphen
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- Pseudorandom generators for space-bounded computation
- Log-space constructible universal traversal sequences for cycles of length O(\(n^{4.03}\)).
- Universal traversal sequences for expander graphs
- Piecemeal graph exploration by a mobile robot.
- The power of a pebble: Exploring and mapping directed graphs
- On-line parallel heuristics, processor scheduling and robot searching under the competitive framework
- Lower bounds on universal traversal sequences based on chains of length five
- Pseudorandomness for network algorithms
- Bounds on Universal Sequences
- Universal traversal sequences for paths and cycles
- How to learn an unknown environment. I
- Automata and Labyrinths
- Online Navigation in a Room
- Navigating in Unfamiliar Geometric Terrain
- Exploring an unknown graph
- Tree exploration with little memory
- Exploring Unknown Undirected Graphs
- Exploring Unknown Environments
- STACS 2004
- Mathematical Foundations of Computer Science 2004
- LATIN 2004: Theoretical Informatics
This page was built for publication: Graph exploration by a finite automaton
