Graph exploration by a finite automaton
From MaRDI portal
Publication:2575752
DOI10.1016/J.TCS.2005.07.014zbMATH Open1081.68045OpenAlexW2039936247MaRDI QIDQ2575752FDOQ2575752
Authors: Pierre Fraigniaud, David Ilcinkas, Guy Peer, Andrzej Pelc, David Peleg 
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
Recommendations
Cites Work
- Piecemeal graph exploration by a mobile robot.
- The power of a pebble: Exploring and mapping directed graphs
- Navigating in Unfamiliar Geometric Terrain
- Exploring an unknown graph
- How to learn an unknown environment. I
- Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
- Pseudorandomness for network algorithms
- Tree exploration with little memory
- Exploring Unknown Environments
- STACS 2004
- Online Navigation in a Room
- Pseudorandom generators for space-bounded computation
- Optimal constrained graph exploration
- Automaten in planaren Graphen
- Automata and Labyrinths
- On-line parallel heuristics, processor scheduling and robot searching under the competitive framework
- Title not available (Why is that?)
- Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques
- Universal traversal sequences for expander graphs
- Bounds on Universal Sequences
- Universal traversal sequences for paths and cycles
- Universal sequences for complete graphs
- Mathematical Foundations of Computer Science 2004
- Exploring Unknown Undirected Graphs
- LATIN 2004: Theoretical Informatics
- Log-space constructible universal traversal sequences for cycles of length O(\(n^{4.03}\)).
- Lower bounds on universal traversal sequences based on chains of length five
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
Cited In (70)
- Black hole search in dynamic cactus graph
- Graph exploration by a deterministic memoryless automaton with pebbles
- Invited paper: One bit agent memory is enough for snap-stabilizing perpetual exploration of cactus graphs with distinguishable cycles
- Complexity of the emptiness problem for graph-walking automata and for tilings with star subgraphs
- Homomorphisms and inverse homomorphisms on graph-walking automata
- Efficient live exploration of a dynamic ring with mobile robots
- A time to cast away stones
- Exploration of High-Dimensional Grids by Finite State Machines
- Tight bounds for deterministic high-dimensional grid exploration
- Evacuation of equilateral triangles by mobile agents of limited communication range
- Fast dispersion of mobile robots on arbitrary graphs
- Title not available (Why is that?)
- Reversibility of computations in graph-walking automata
- Optimal dispersion on an anonymous ring in the presence of weak Byzantine robots
- The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks
- A general lower bound for collaborative tree exploration
- Title not available (Why is that?)
- An improved lower bound for competitive graph exploration
- Distributed graph searching with a sense of direction
- Fault-tolerant dispersion of mobile robots
- Building a nest by an automaton
- State complexity of transforming graph-walking automata to halting, returning and reversible
- Graph automata: Natural expression of self-reproduction
- Ping pong in dangerous graphs: optimal black hole search with pebbles
- A probabilistic model for the interaction of an agent with a network environment
- Two-agent tree evacuation
- Derandomizing random walks in undirected graphs using locally fair exploration strategies
- Robustness of the rotor-router mechanism
- An improved strategy for exploring a grid polygon
- Black hole search in directed graphs
- Collaborative exploration of trees by energy-constrained mobile robots
- Dispersion of mobile robots on directed anonymous graphs
- Memory Efficient Anonymous Graph Exploration
- Exploring a Dynamic Ring Without Landmark
- Chaotic Traversal (CHAT): Very Large Graphs Traversal Using Chaotic Dynamics
- Connected reconfiguration of lattice-based cellular structures by finite-memory robots
- LABEL-GUIDED GRAPH EXPLORATION WITH ADJUSTABLE RATIO OF LABELS
- Fast periodic graph exploration with constant memory
- Distributed exploration of dynamic rings
- More efficient periodic traversal in anonymous undirected graphs
- Tree exploration with little memory
- Mathematical Foundations of Computer Science 2004
- How many ants does it take to find the food?
- Exploring an unknown dangerous graph with a constant number of tokens
- Time optimal algorithms for black hole search in rings
- Title not available (Why is that?)
- Structural Information and Communication Complexity
- Homomorphisms on graph-walking automata
- Exploring a dynamic ring without landmark
- Shape recognition by a finite automaton robot
- Exploration of dynamic networks: tight bounds on the number of agents
- Lower and upper competitive bounds for online directed graph exploration
- STACS 2004
- Collision-free network exploration
- Exploration of High-Dimensional Grids by Finite Automata
- Exploration of Time-Varying Connected Graphs with Silent Agents
- Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens
- On defining linear orders by automata
- Recognition of graphs by automata
- Distributed chasing of network intruders
- On the Power of Local Orientations
- Anonymous graph exploration without collision by mobile robots
- Traversal of an unknown directed graph by a finite robot
- Graph decomposition for memoryless periodic exploration
- Wireless evacuation on \(m\) rays with \(k\) searchers
- Automata, Languages and Programming
- Collaborative Exploration by Energy-Constrained Mobile Robots
- Impact of memory size on graph exploration capability
- State complexity of union and intersection on graph-walking automata
- Graph Decomposition for Improving Memoryless Periodic Exploration
This page was built for publication: Graph exploration by a finite automaton
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2575752)
