Impact of memory size on graph exploration capability

DOI10.1016/J.DAM.2007.11.001zbMath1155.68055OpenAlexW2025264288MaRDI QIDQ947116

Pierre Fraigniaud, Andrzej Pelc, David Ilcinkas

Publication date: 29 September 2008

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2007.11.001

zbMATH Keywords

finite automatonmobile agentgraph explorationrobotmemory size

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

Graph Decomposition for Improving Memoryless Periodic Exploration ⋮ Online graph exploration: New results on old and new algorithms ⋮ Graph decomposition for memoryless periodic exploration ⋮ Exploration of dynamic networks: tight bounds on the number of agents ⋮ Online Graph Exploration: New Results on Old and New Algorithms ⋮ Weighted nearest neighbor algorithms for the graph exploration problem on cycles ⋮ Black Hole Search in Directed Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Universal sequences for complete graphs
• Universal traversal sequences of length \(n^{0(\log \,n)}\) for cliques
• Automaten in planaren Graphen
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Pseudorandom generators for space-bounded computation
• Log-space constructible universal traversal sequences for cycles of length O(\(n^{4.03}\)).
• Universal traversal sequences for expander graphs
• On the cover time of random walks on graphs
• Piecemeal graph exploration by a mobile robot.
• The power of a pebble: Exploring and mapping directed graphs
• Lower bounds on universal traversal sequences based on chains of length five
• Pseudorandomness for network algorithms
• Bounds on Universal Sequences
• Universal traversal sequences for paths and cycles
• Automata and Labyrinths
• Exploring an unknown graph
• Tree exploration with little memory
• Exploring Unknown Undirected Graphs
• Exploring Unknown Environments
• STACS 2004
• Mathematical Foundations of Computer Science 2004

This page was built for publication: Impact of memory size on graph exploration capability