More efficient periodic traversal in anonymous undirected graphs

DOI10.1016/J.TCS.2012.01.035MaRDI QIDQ442265zbMATHOpenAlexFDO

Authors Jurek Czyzowicz, Stefan Dobrev, Leszek Gąsieniec, David Ilcinkas, Jesper Jansson, Ralf Klasing, Ioannis Lignos, Russell Martin, Kunihiko Sadakane, Wing-Kin Sung

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

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05) Agent technology and artificial intelligence (68T42)

Recommendations

• More efficient periodic traversal in anonymous undirected graphs
• Fast periodic graph exploration with constant memory
• Fast Periodic Graph Exploration with Constant Memory
• Setting Port Numbers for Fast Graph Exploration
• Setting port numbers for fast graph exploration

Cites work

• Automata and Labyrinths
• Automaten in planaren Graphen
• Fast periodic graph exploration with constant memory
• Graph Decomposition for Improving Memoryless Periodic Exploration
• Setting port numbers for fast graph exploration
• Space Lower Bounds for Maze Threadability on Restricted Machines
• Structural Information and Communication Complexity
• The Planar Hamiltonian Circuit Problem is NP-Complete
• Undirected ST-connectivity in log-space

Cited in

(13)

• More efficient periodic traversal in anonymous undirected graphs
• More agents may decrease global work: a case in butterfly decontamination
• Graph decomposition for memoryless periodic exploration
• Graph Decomposition for Improving Memoryless Periodic Exploration
• Structural Information and Communication Complexity
• Memory Efficient Anonymous Graph Exploration
• Improved periodic data retrieval in asynchronous rings with a faulty host
• Setting Port Numbers for Fast Graph Exploration
• Fast Periodic Graph Exploration with Constant Memory
• Setting ports in an anonymous network: how to reduce the level of symmetry?
• Exploration of periodically varying graphs
• Invited paper: One bit agent memory is enough for snap-stabilizing perpetual exploration of cactus graphs with distinguishable cycles
• Fast periodic graph exploration with constant memory

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

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