Graph Decomposition for Improving Memoryless Periodic Exploration

DOI10.1007/978-3-642-03816-7_43MaRDI QIDQ3182950zbMATH OpenOpenAlexFDO

Authors Adrian Kosowski, Alfredo Navarra

Publication date 16 October 2009

Published in Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-03816-7_43

zbMATH Keywords

graph decompositiongraph labelinglabeling schemeperiodic explorationmemoryless robot

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Artificial intelligence for robotics (68T40)

Recommendations

• Graph decomposition for 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 exploration by a finite automaton
• Impact of memory size on graph exploration capability
• 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

(5)

• Invited paper: One bit agent memory is enough for snap-stabilizing perpetual exploration of cactus graphs with distinguishable cycles
• Synchronous black hole search in directed graphs
• Universal systems of oblivious mobile robots
• More efficient periodic traversal in anonymous undirected graphs
• Graph decomposition for memoryless periodic exploration

This page was built for publication: Graph Decomposition for Improving Memoryless Periodic Exploration

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