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 (6)

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

This page was built for publication: More efficient periodic traversal in anonymous undirected graphs