Fast periodic graph exploration with constant memory

DOI10.1016/J.JCSS.2007.09.004MaRDI QIDQ931724zbMATH OpenOpenAlexFDO

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

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

penaltyperiodfinite automatonfull degreeport number

Mathematics Subject Classification ID

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

Recommendations

• Fast Periodic Graph Exploration with Constant Memory
• More efficient periodic traversal in anonymous undirected graphs
• Setting port numbers for fast graph exploration
• Setting Port Numbers for Fast Graph Exploration
• More efficient periodic traversal in anonymous undirected graphs

Cites work

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

Cited in

(20)

• More efficient periodic traversal in anonymous undirected graphs
• Label-guided graph exploration by a finite automaton
• Bamboo garden trimming problem: priority schedulings
• Explore and repair graphs with black holes using mobile entities
• Automata, Languages and Programming
• Graph decomposition for memoryless periodic exploration
• Graph Decomposition for Improving Memoryless Periodic Exploration
• Structural Information and Communication Complexity
• Memory Efficient Anonymous Graph Exploration
• LABEL-GUIDED GRAPH EXPLORATION WITH ADJUSTABLE RATIO OF LABELS
• A structured methodology for designing distributed algorithms for mobile entities
• Time and space optimality of rotor-router graph exploration
• Setting Port Numbers for Fast Graph Exploration
• Fast Periodic Graph Exploration with Constant Memory
• Setting ports in an anonymous network: how to reduce the level of symmetry?
• Synchronous black hole search in directed graphs
• Exploration of periodically varying graphs
• 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
• More efficient periodic traversal in anonymous undirected graphs

This page was built for publication: Fast periodic graph exploration with constant memory

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