Impact of memory size on graph exploration capability

DOI10.1016/J.DAM.2007.11.001MaRDI QIDQ947116zbMATH OpenOpenAlexFDO

Authors Pierre Fraigniaud, David Ilcinkas, Andrzej Pelc

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

mobile agentfinite automatongraph explorationrobotmemory size

Mathematics Subject Classification ID

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

Recommendations

• Graph exploration by a finite automaton
• Mathematical Foundations of Computer Science 2004
• STACS 2004
• Tree exploration with logarithmic memory
• Automata, Languages and Programming

Cites work

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

Cited in

(8)

• Weighted nearest neighbor algorithms for the graph exploration problem on cycles
• Online Graph Exploration: New Results on Old and New Algorithms
• Black hole search in directed graphs
• Memory Efficient Anonymous Graph Exploration
• Online graph exploration: New results on old and new algorithms
• Exploration of dynamic networks: tight bounds on the number of agents
• Graph decomposition for memoryless periodic exploration
• Graph Decomposition for Improving Memoryless Periodic Exploration

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

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