Map construction of unknown graphs by multiple agents

DOI10.1016/j.tcs.2007.05.011zbMath1124.68078MaRDI QIDQ2456354

Shantanu Das, Shay Kutten, Paola Flocchini, Nicola Santoro, Amiya Nayak

Publication date: 18 October 2007

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2007.05.011

zbMATH Keywords

rendezvous; leader election; graph exploration; anonymous mobile agents; labelled map construction

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

Related Items

Election and rendezvous with incomparable labels, Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens, Graph exploration with robot swarms

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimal graph exploration without good maps
• Rendezvous and election of mobile agents: Impact of sense of direction
• \((p-1)/(p+1)\)-approximate algorithms for \(p\)-traveling salesmen problems on a tree with minmax objective
• The theory of search games and rendezvous.
• Comparison of initial conditions for distributed algorithms on anonymous networks
• A Distributed Algorithm for Minimum-Weight Spanning Trees
• Distributed Algorithms For Unidirectional Networks
• Tree exploration with little memory
• Exploring Unknown Undirected Graphs
• Exploring Unknown Environments
• STACS 2004
• Depth-First Search and Linear Graph Algorithms
• Structural Information and Communication Complexity
• Algorithms - ESA 2003
• LATIN 2004: Theoretical Informatics
• LATIN 2004: Theoretical Informatics