Memory Efficient Anonymous Graph Exploration
From MaRDI portal
Publication:5302040
DOI10.1007/978-3-540-92248-3_2zbMath1202.68277OpenAlexW1569088102MaRDI QIDQ5302040
Tomasz Radzik, Leszek Gąsieniec
Publication date: 20 January 2009
Published in: Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-540-92248-3_2
Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Random walks on graphs (05C81)
Related Items (12)
Graph Decomposition for Improving Memoryless Periodic Exploration ⋮ The multi-agent rotor-router on the ring: a deterministic alternative to parallel random walks ⋮ Robustness of the rotor-router mechanism ⋮ Online graph exploration: New results on old and new algorithms ⋮ Explore and repair graphs with black holes using mobile entities ⋮ Exploration of Time-Varying Connected Graphs with Silent Agents ⋮ Zero-memory graph exploration with unknown inports ⋮ Graph decomposition for memoryless periodic exploration ⋮ Reconstructing Markov processes from independent and anonymous experiments ⋮ Online Graph Exploration: New Results on Old and New Algorithms ⋮ Connected reconfiguration of lattice-based cellular structures by finite-memory robots ⋮ Setting Ports in an Anonymous Network: How to Reduce the Level of Symmetry?
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the impact of sense of direction on message complexity
- More efficient periodic traversal in anonymous undirected graphs
- Optimal graph exploration without good maps
- The cover time of a regular expander is O(n log n)
- Universal sequences for complete graphs
- Fast periodic graph exploration with constant memory
- A randomized algorithm for the joining protocol in dynamic distributed networks
- Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques
- Automaten in planaren Graphen
- The electrical resistance of a graph captures its commute and cover times
- Collecting coupons on trees, and the cover time of random walks
- 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
- Universal traversal sequences with backtracking.
- A distributed ant algorithm for efficiently patrolling a network
- Lower bounds on universal traversal sequences based on chains of length five
- Deterministic random walks on the integers
- Graph exploration by a finite automaton
- Pseudorandomness for network algorithms
- Optimal constrained graph exploration
- Multiple Random Walks in Random Regular Graphs
- Multiple cover time
- Simulating a Random Walk with Constant Error
- Bounds on Universal Sequences
- Crawling on web graphs
- Undirected ST-connectivity in log-space
- Setting Port Numbers for Fast Graph Exploration
- Universal traversal sequences for paths and cycles
- How to learn an unknown environment. I
- Space Lower Bounds for Maze Threadability on Restricted Machines
- On the time taken by random walks on finite groups to visit every state
- A Technique for Lower Bounding the Cover Time
- The Planar Hamiltonian Circuit Problem is NP-Complete
- Automata and Labyrinths
- Trading Space for Time in Undirected s-t Connectivity
- A tight upper bound on the cover time for random walks on graphs
- Navigating in Unfamiliar Geometric Terrain
- Traversing Directed Eulerian Mazes
- Impact of topographic information on graph exploration efficiency
- Sense of direction: Definitions, properties, and classes
- Exploring an unknown graph
- Tree exploration with little memory
- A tight lower bound on the cover time for random walks on graphs
- Exploring Unknown Environments
- Interval routing schemes allow broadcasting with linear message-complexity (extended abstract)
- Many Random Walks Are Faster Than One
- STACS 2004
- The Cover Time of Random Regular Graphs
- Deterministic Random Walks on the Two-Dimensional Grid
- Structural Information and Communication Complexity
- Automata, Languages and Programming
This page was built for publication: Memory Efficient Anonymous Graph Exploration