Graph decomposition for memoryless periodic exploration

DOI10.1007/s00453-011-9518-1zbMath1241.05114OpenAlexW2072637783MaRDI QIDQ2429354

Alfredo Navarra, Adrian Kosowski

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

labelingoblivious robotsanonymous graphexploration algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) 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) Vertex degrees (05C07)

Related Items

Characterizing the computational power of mobile robots on graphs and implications for the Euclidean plane, EFFICIENT GRID EXPLORATION WITH A STATIONARY TOKEN, Explore and repair graphs with black holes using mobile entities, 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, Bamboo garden trimming problem: priority schedulings, Setting Ports in an Anonymous Network: How to Reduce the Level of Symmetry?

Cites Work

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