On the public citation graph
Tight Bounds for Undirected Graph Exploration with Pebbles and Multiple Agents
0 signed · 57 inferred · view as graph
Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.
Is this your work? Sign in with ORCID and put your name on the
claims that are yours.
Reference health. See whether every reference in this work resolves to a
known work and none has been retracted — and get a dated CiteStamped
badge you can embed.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1002/(sici)1097-0118(199911)32:3<265::aid-jgt6>3.0.co;2-8openalex-snapshot
Exploring an unknown graph
inferredcites →https://doi.org/10.1002/(sici)1097-0118(199911)32:3<265::aid-jgt6>3.3.co;2-#openalex-snapshot
Exploring an unknown graph
inferredcites →https://doi.org/10.1006/inco.2001.3081openalex-snapshot
The Power of a Pebble: Exploring and Mapping Directed Graphs
inferredcites →https://doi.org/10.1007/11561071_4openalex-snapshot
Exploring an Unknown Graph Efficiently
inferredcites →https://doi.org/10.1007/11685654_1openalex-snapshot
The Reduced Automata Technique for Graph Exploration Space Lower Bounds
inferredcites →https://doi.org/10.1007/3-540-10854-8_47openalex-snapshot
One pebble does not suffice to search plane labyrinths
inferredcites →https://doi.org/10.1007/978-1-4020-9688-4_3openalex-snapshot
An analysis of several heuristics for the traveling salesman problem
inferredcites →https://doi.org/10.1007/978-3-540-24749-4_22openalex-snapshot
Digraphs Exploration with Little Memory
inferredcites →https://doi.org/10.1007/978-3-642-17653-1_10openalex-snapshot
Constructing a Map of an Anonymous Graph: Applications of Universal Sequences
inferredcites →https://doi.org/10.1007/bf01305237openalex-snapshot
Pseudorandom generators for space-bounded computation
inferredcites →https://doi.org/10.1007/s00453-011-9572-8openalex-snapshot
Mapping Simple Polygons: How Robots Benefit from Looking Back
inferredcites →https://doi.org/10.1016/0146-664x(74)90017-3openalex-snapshot
Pebble automata on arrays
inferredcites →https://doi.org/10.1016/0304-3975(94)90155-4openalex-snapshot
Constructing competitive tours from local information
inferredcites →https://doi.org/10.1016/j.dam.2007.11.001openalex-snapshot
Impact of memory size on graph exploration capability
inferredcites →https://doi.org/10.1016/j.jalgor.2003.10.002openalex-snapshot
Tree exploration with little memory
inferredcites →https://doi.org/10.1016/j.tcs.2005.07.014openalex-snapshot
Graph exploration by a finite automaton
inferredcites →https://doi.org/10.1016/j.tcs.2012.06.034openalex-snapshot
Online graph exploration: New results on old and new algorithms
inferredcites →https://doi.org/10.1016/j.tcs.2015.11.017openalex-snapshot
Lower and upper competitive bounds for online directed graph exploration
inferredcites →https://doi.org/10.1016/s0022-0000(02)00023-5openalex-snapshot
Universal traversal sequences with backtracking
inferredcites →https://doi.org/10.1016/s0022-0000(73)80031-5openalex-snapshot
Maze recognizing automata and nondeterministic tape complexity
inferredcites →https://doi.org/10.1109/70.105395openalex-snapshot
Robotic exploration as graph construction
inferredcites →https://doi.org/10.1109/sfcs.1978.30openalex-snapshot
On the power of the compass (or, why mazes are easier to search than graphs)
inferredcites →https://doi.org/10.1109/sfcs.1979.34openalex-snapshot
Random walks, universal traversal sequences, and the complexity of maze problems
inferredcites →https://doi.org/10.1109/sfcs.1994.365703openalex-snapshot
The power of team exploration: two robots can learn unlabeled directed graphs
inferredcites →https://doi.org/10.1137/0206041openalex-snapshot
An Analysis of Several Heuristics for the Traveling Salesman Problem
inferredcites →https://doi.org/10.1137/0209048openalex-snapshot
Space Lower Bounds for Maze Threadability on Restricted Machines
inferredcites →https://doi.org/10.1137/s0097539791194931openalex-snapshot
Navigating in Unfamiliar Geometric Terrain
inferredcites →https://doi.org/10.1137/s009753979732428xopenalex-snapshot
Exploring Unknown Environments
inferredcites →https://doi.org/10.1145/1391289.1391291openalex-snapshot
Undirected connectivity in log-space
inferredcites →https://doi.org/10.1145/1921659.1921663openalex-snapshot
Tree exploration with logarithmic memory
inferredcites →https://doi.org/10.1145/274787.274788openalex-snapshot
How to learn an unknown environment. I
inferredcites →https://doi.org/10.1145/62212.62260openalex-snapshot
Polynomial universal traversing sequences for cycles are constructible
inferredcites →https://doi.org/10.1587/transinf.e92.d.1620openalex-snapshot
The Online Graph Exploration Problem on Restricted Graphs
What points at this work
Incoming claims: where this work appears in other papers’ reference lists and arguments.
inferred← citeshttps://doi.org/10.1007/978-3-030-79527-6_13openalex-snapshot
Pebble Guided Near Optimal Treasure Hunt in Anonymous Graphs
inferred← citeshttps://doi.org/10.1007/978-3-030-93489-7_11openalex-snapshot
State Complexity of Union and Intersection on Graph-Walking Automata
inferred← citeshttps://doi.org/10.1007/978-3-031-07469-1_14openalex-snapshot
Homomorphisms on Graph-Walking Automata
inferred← citeshttps://doi.org/10.1007/978-3-031-21017-4_2openalex-snapshot
Invited Paper: One Bit Agent Memory is Enough for Snap-Stabilizing Perpetual Exploration of Cactus Graphs with Distinguishable Cycles
inferred← citeshttps://doi.org/10.1007/978-3-031-21534-6_8openalex-snapshot
The Space Complexity of Undirected Graph Exploration
inferred← citeshttps://doi.org/10.1007/978-3-031-32733-9_11openalex-snapshot
Zero-Memory Graph Exploration with Unknown Inports
inferred← citeshttps://doi.org/10.1007/978-3-031-40247-0_18openalex-snapshot
A Time to Cast Away Stones
inferred← citeshttps://doi.org/10.1007/978-3-032-26465-7_14openalex-snapshot
Cow Path by Finite Agent: Time vs Pebbles
inferred← citeshttps://doi.org/10.1016/j.dam.2024.05.024openalex-snapshot
Graph exploration by a deterministic memoryless automaton with pebbles
inferred← citeshttps://doi.org/10.1016/j.ic.2023.105011openalex-snapshot
State complexity of transforming graph-walking automata to halting, returning and reversible
inferred← citeshttps://doi.org/10.1016/j.ic.2025.105380openalex-snapshot
Collision-free exploration by mobile agents using pebbles
inferred← citeshttps://doi.org/10.1016/j.jcss.2025.103725openalex-snapshot
Exploration of graphs with excluded minors
inferred← citeshttps://doi.org/10.1016/j.tcs.2020.06.007openalex-snapshot
Online graph exploration on a restricted graph class: Optimal solutions for tadpole graphs
inferred← citeshttps://doi.org/10.1016/j.tcs.2021.04.003openalex-snapshot
An improved lower bound for competitive graph exploration
inferred← citeshttps://doi.org/10.1016/j.tcs.2022.04.011openalex-snapshot
Pebble guided optimal treasure hunt in anonymous graphs
inferred← citeshttps://doi.org/10.1016/j.tcs.2023.114197openalex-snapshot
Homomorphisms and inverse homomorphisms on graph-walking automata
inferred← citeshttps://doi.org/10.1142/s0129054124420012openalex-snapshot
State Complexity of Boolean Operations on Graph-Walking Automata
inferred← citeshttps://doi.org/10.1142/s0129054125410023openalex-snapshot
A Time to Cast Away Stones: On a Family of Pebble Automata
inferred← citeshttps://doi.org/10.1145/3700838.3700863openalex-snapshot
Collision-free Exploration by Mobile Agents Using Pebbles
Editorial review for independent work. ICSAC — the Institute for Complexity
Science and Advanced Computing — runs a structured editorial panel for researchers
publishing outside journals, and publishes on CiteStamp rails. Submission is free
and goes through ORCID: icsacinstitute.org/submit.