More efficient periodic traversal in anonymous undirected graphs
DOI10.1016/j.tcs.2012.01.035zbMath1246.68169OpenAlexW2174851824MaRDI QIDQ442265
David Ilcinkas, Jurek Czyzowicz, Jesper Jansson, Stefan Dobrev, Leszek Gąsieniec, Ralf Klasing, Wing-Kin Sung, Ioannis Lignos, Kunihiko Sadakane, Russell Martin
Publication date: 10 August 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.01.035
graph explorationalgorithms and data structuresconstant-memory agentoblivious agentperiodic graph traversalthree-layer partition
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Data structures (68P05) Agent technology and artificial intelligence (68T42)
Related Items
Cites Work
- Fast periodic graph exploration with constant memory
- Setting port numbers for fast graph exploration
- Automaten in planaren Graphen
- Graph Decomposition for Improving Memoryless Periodic Exploration
- Undirected ST-connectivity in log-space
- Space Lower Bounds for Maze Threadability on Restricted Machines
- The Planar Hamiltonian Circuit Problem is NP-Complete
- Automata and Labyrinths
- Structural Information and Communication Complexity