The power of a pebble: Exploring and mapping directed graphs

DOI10.1006/inco.2001.3081zbMath1012.68202OpenAlexW2047087577MaRDI QIDQ1854539

Yanyan Li

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: http://nrs.harvard.edu/urn-3:HUL.InstRepos:2958489

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Artificial intelligence for robotics (68T40)

Related Items (35)

OPTIMAL CONSTRUCTION OF SENSE OF DIRECTION IN A TORUS BY A MOBILE AGENT ⋮ TIME OPTIMAL ALGORITHMS FOR BLACK HOLE SEARCH IN RINGS ⋮ Memory Efficient Anonymous Graph Exploration ⋮ Lower and upper competitive bounds for online directed graph exploration ⋮ Robustness of the rotor-router mechanism ⋮ Grid exploration by a swarm of autonomous robots with minimum repetitions ⋮ Exploring an unknown dangerous graph with a constant number of tokens ⋮ Ping pong in dangerous graphs: optimal black hole search with pebbles ⋮ Gathering of robots on meeting-points: feasibility and optimal resolution algorithms ⋮ Drawing maps with advice ⋮ Exploration of Faulty Hamiltonian Graphs ⋮ Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens ⋮ Building a nest by an automaton ⋮ Fast periodic graph exploration with constant memory ⋮ Derandomizing random walks in undirected graphs using locally fair exploration strategies ⋮ Setting port numbers for fast graph exploration ⋮ LABEL-GUIDED GRAPH EXPLORATION WITH ADJUSTABLE RATIO OF LABELS ⋮ Impact of memory size on graph exploration capability ⋮ Tree exploration with advice ⋮ Linear search by a pair of distinct-speed robots ⋮ Trade-offs between the size of advice and broadcasting time in trees ⋮ Communication algorithms with advice ⋮ Unnamed Item ⋮ Wireless evacuation on \(m\) rays with \(k\) searchers ⋮ A general lower bound for collaborative tree exploration ⋮ Time versus cost tradeoffs for deterministic rendezvous in networks ⋮ Graph searching with advice ⋮ Exploration of High-Dimensional Grids by Finite Automata ⋮ Linear Search by a Pair of Distinct-Speed Robots ⋮ Graph exploration with robot swarms ⋮ More Efficient Periodic Traversal in Anonymous Undirected Graphs ⋮ Graph exploration by a finite automaton ⋮ Exploring sparse graphs with advice ⋮ Fast collaborative graph exploration ⋮ Convergecast and broadcast by power-aware mobile agents

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Searching in the plane
• Shortest paths without a map
• Learning regular sets from queries and counterexamples
• Efficient learning of typical finite automata from random walks
• Piecemeal graph exploration by a mobile robot.
• Inference of finite automata using homing sequences
• How to learn an unknown environment. I
• On behaviour of automata in labyrinths
• Diversity-based inference of finite automata
• Online Navigation in a Room
• Navigating in Unfamiliar Geometric Terrain

This page was built for publication: The power of a pebble: Exploring and mapping directed graphs