More efficient periodic traversal in anonymous undirected graphs

DOI10.1016/J.TCS.2012.01.035zbMATH Open1246.68169OpenAlexW2174851824MaRDI QIDQ442265FDOQ442265

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

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

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)

Cites Work

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

Cited In (13)

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

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)