Exploring an unknown graph
From MaRDI portal
Publication:4718736
DOI<link itemprop=identifier href="https://doi.org/10.1002/(SICI)1097-0118(199911)32:3<265::AID-JGT6>3.0.CO;2-8" /><265::AID-JGT6>3.0.CO;2-8 10.1002/(SICI)1097-0118(199911)32:3<265::AID-JGT6>3.0.CO;2-8zbMath0941.68099OpenAlexW4256624975MaRDI QIDQ4718736
Christos H. Papadimitriou, Xiaotie Deng
Publication date: 3 January 2000
Full work available at URL: https://doi.org/10.1002/(sici)1097-0118(199911)32:3<265::aid-jgt6>3.0.co;2-8
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (46)
An improved lower bound for competitive graph exploration ⋮ 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 ⋮ Computing without communicating: ring exploration by asynchronous oblivious robots ⋮ EFFICIENT GRID EXPLORATION WITH A STATIONARY TOKEN ⋮ Exploring a dynamic ring without landmark ⋮ Distributed exploration of dynamic rings ⋮ Robustness of the rotor-router mechanism ⋮ Tight bounds for black hole search with scattered agents in synchronous rings ⋮ Exploration of Time-Varying Connected Graphs with Silent Agents ⋮ Efficient live exploration of a dynamic ring with mobile robots ⋮ The beachcombers' problem: walking and searching with mobile robots ⋮ How many ants does it take to find the food? ⋮ Exploring an unknown dangerous graph with a constant number of tokens ⋮ Approximate sequencing for variable length tasks. ⋮ On the Power of Local Orientations ⋮ Ping pong in dangerous graphs: optimal black hole search with pebbles ⋮ Drawing maps with advice ⋮ Exploration of Faulty Hamiltonian Graphs ⋮ Deterministic network exploration by a single agent with Byzantine tokens ⋮ Searching for a black hole in arbitrary networks: optimal mobile agents protocols ⋮ The \(k\)-server problem ⋮ A tight lower bound for semi-synchronous collaborative grid exploration ⋮ 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 ⋮ Map construction of unknown graphs by multiple agents ⋮ Setting port numbers for fast graph exploration ⋮ Exploration of dynamic networks: tight bounds on the number of agents ⋮ Impact of memory size on graph exploration capability ⋮ Tree exploration with advice ⋮ Online graph exploration algorithms for cycles and trees by multiple searchers ⋮ Remembering without memory: tree exploration by asynchronous oblivious robots ⋮ Optimal graph exploration without good maps ⋮ Unnamed Item ⋮ A general lower bound for collaborative tree exploration ⋮ Time versus cost tradeoffs for deterministic rendezvous in networks ⋮ Black Hole Search with Finite Automata Scattered in a Synchronous Torus ⋮ More Efficient Periodic Traversal in Anonymous Undirected Graphs ⋮ A tight lower bound for semi-synchronous collaborative grid exploration ⋮ Graph exploration by a finite automaton ⋮ Graph exploration by energy-sharing mobile agents ⋮ Convergecast and broadcast by power-aware mobile agents
Cites Work
This page was built for publication: Exploring an unknown graph
