Impact of memory size on graph exploration capability
From MaRDI portal
Publication:947116
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
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
