Memory Efficient Anonymous Graph Exploration

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

Mathematics Subject Classification ID

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