Map construction of unknown graphs by multiple agents

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

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

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

rendezvousleader electiongraph explorationanonymous mobile agentslabelled map construction

Mathematics Subject Classification ID

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

Related Items (21)

Search by a metamorphic robotic system in a finite 2D square grid ⋮ Lower and upper competitive bounds for online directed graph exploration ⋮ Computing without communicating: ring exploration by asynchronous oblivious robots ⋮ EFFICIENT GRID EXPLORATION WITH A STATIONARY TOKEN ⋮ Exploring a dynamic ring without landmark ⋮ Distributed exploration of dynamic rings ⋮ Beyond Rings: Gathering in 1-Interval Connected Graphs ⋮ Efficient live exploration of a dynamic ring with mobile robots ⋮ The beachcombers' problem: walking and searching with mobile robots ⋮ Exploring an unknown dangerous graph with a constant number of tokens ⋮ How many oblivious robots can explore a line ⋮ Ping pong in dangerous graphs: optimal black hole search with pebbles ⋮ Deterministic network exploration by a single agent with Byzantine tokens ⋮ Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens ⋮ Election and rendezvous with incomparable labels ⋮ Computing by Mobile Robotic Sensors ⋮ Beachcombing on strips and islands ⋮ Connected reconfiguration of lattice-based cellular structures by finite-memory robots ⋮ Graph exploration with robot swarms ⋮ Exploring sparse graphs with advice ⋮ Distributed graph searching with a sense of direction

Cites Work

• 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
• Exploring an unknown graph
• 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

This page was built for publication: Map construction of unknown graphs by multiple agents