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

zbMATH Keywords

graph explorationalgorithms and data structuresconstant-memory agentoblivious agentperiodic graph traversalthree-layer partition

Mathematics Subject Classification ID

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

Memory Efficient Anonymous Graph Exploration, Graph Decomposition for Improving Memoryless Periodic Exploration, More agents may decrease global work: a case in butterfly decontamination, Improved periodic data retrieval in asynchronous rings with a faulty host, Invited paper: One bit agent memory is enough for snap-stabilizing perpetual exploration of cactus graphs with distinguishable cycles, Setting Ports in an Anonymous Network: How to Reduce the Level of Symmetry?

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