Graph decomposition for memoryless periodic exploration

DOI10.1007/S00453-011-9518-1MaRDI QIDQ2429354zbMATH OpenOpenAlexFDO

Authors Adrian Kosowski, Alfredo Navarra

Publication date 26 April 2012

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00453-011-9518-1

zbMATH Keywords

anonymous graphexploration algorithmlabelingoblivious robots

Mathematics Subject Classification ID

Vertex degrees (05C07) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Graph Decomposition for Improving Memoryless Periodic Exploration
• Fast periodic graph exploration with constant memory
• Fast Periodic Graph Exploration with Constant Memory
• More efficient periodic traversal in anonymous undirected graphs
• More efficient periodic traversal in anonymous undirected graphs

Cites work

• Automata and Labyrinths
• Automata, Languages and Programming
• Automaten in planaren Graphen
• Fast periodic graph exploration with constant memory
• Graph Decomposition for Improving Memoryless Periodic Exploration
• Graph exploration by a finite automaton
• Impact of memory size on graph exploration capability
• Labeling schemes for tree representation
• Memory Efficient Anonymous Graph Exploration
• More efficient periodic traversal in anonymous undirected graphs
• Setting port numbers for fast graph exploration
• Space Lower Bounds for Maze Threadability on Restricted Machines
• Structural Information and Communication Complexity
• Undirected ST-connectivity in log-space

Cited in

(8)

• Characterizing the computational power of mobile robots on graphs and implications for the Euclidean plane
• Bamboo garden trimming problem: priority schedulings
• Setting ports in an anonymous network: how to reduce the level of symmetry?
• Efficient grid exploration with a stationary token
• Graph Decomposition for Improving Memoryless Periodic Exploration
• Exploration of Time-Varying Connected Graphs with Silent Agents
• Invited paper: One bit agent memory is enough for snap-stabilizing perpetual exploration of cactus graphs with distinguishable cycles
• Explore and repair graphs with black holes using mobile entities

This page was built for publication: Graph decomposition for memoryless periodic exploration

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2429354)