Fast periodic graph exploration with constant memory

DOI10.1016/j.jcss.2007.09.004zbMath1149.68048OpenAlexW1981557449MaRDI QIDQ931724

Ralf Klasing, Russell Martin, Leszek Gąsieniec, Xiaohui Zhang, Alfredo Navarra

Publication date: 26 June 2008

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2007.09.004

zbMATH Keywords

finite automatonperiodpenaltyfull degreeport number

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Memory Efficient Anonymous Graph Exploration, Graph Decomposition for Improving Memoryless Periodic Exploration, Explore and repair graphs with black holes using mobile entities, Exploration of Time-Varying Connected Graphs with Silent Agents, A structured methodology for designing distributed algorithms for mobile entities, Invited paper: One bit agent memory is enough for snap-stabilizing perpetual exploration of cactus graphs with distinguishable cycles, Graph decomposition for memoryless periodic exploration, More efficient periodic traversal in anonymous undirected graphs, LABEL-GUIDED GRAPH EXPLORATION WITH ADJUSTABLE RATIO OF LABELS, Bamboo garden trimming problem: priority schedulings, Synchronous black hole search in directed graphs, Setting Ports in an Anonymous Network: How to Reduce the Level of Symmetry?, More Efficient Periodic Traversal in Anonymous Undirected Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Automaten in planaren Graphen
• Piecemeal graph exploration by a mobile robot.
• The power of a pebble: Exploring and mapping directed graphs
• Graph exploration by a finite automaton
• Undirected ST-connectivity in log-space
• Setting Port Numbers for Fast Graph Exploration
• Space Lower Bounds for Maze Threadability on Restricted Machines
• Automata and Labyrinths
• Exploring an unknown graph
• Tree exploration with little memory
• Exploring Unknown Undirected Graphs
• Exploring Unknown Environments
• STACS 2004
• Fast Periodic Graph Exploration with Constant Memory
• Algorithms – ESA 2005
• Structural Information and Communication Complexity
• Automata, Languages and Programming