Collision-free network exploration

DOI10.1016/j.jcss.2016.11.008zbMath1370.68229OpenAlexW2563013149MaRDI QIDQ2396820

Ralf Klasing, Leszek Gąsieniec, Dariusz Dereniowski, Adrian Kosowski, Dominik Pająk, Jurek Czyzowicz

Publication date: 26 May 2017

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://hal.inria.fr/hal-00736276/file/collision-free-exploration.pdf

zbMATH Keywords

mobile agentsnetwork explorationsynchronous agents

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Agent technology and artificial intelligence (68T42)

Cites Work

• Unnamed Item
• A tight upper bound on acquaintance time of graphs
• A note on the acquaintance time of random graphs
• An annotated bibliography on guaranteed graph searching
• Anonymous graph exploration without collision by mobile robots
• Many-to-many routing on trees via matchings
• The theory of search games and rendezvous.
• The acquaintance time of (percolated) random geometric graphs
• Graph exploration by a finite automaton
• Acquaintance Time of Random Graphs Near Connectivity Threshold
• Acquaintance Time of a Graph
• Exclusive Perpetual Ring Exploration without Chirality
• Optimal Bounds for Matching Routing on Trees
• Routing Permutations on Graphs via Matchings
• Approximating the Minimum-Degree Steiner Tree to within One of Optimal
• Exploring Unknown Undirected Graphs
• Exploring Unknown Environments
• Collision-Free Network Exploration
• Matroids and the greedy algorithm