.png){kind=icon}
.png){kind=icon}
Return
Computing Tree Structures in Anonymous Graphs via Mobile Agents
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-032-11127-2_11.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Minimum Spanning Tree (MST) and Breadth -First Search (BFS) tree constructions are classical problems in distributed computing, typically studied in the message -passing model, where static nodes communicate via messages. This paper examines these problems in an agent-based network, where computational devices are modelled as mobile agents that explore a graph and perform computations. Each node serves as a container for agents, and communication occurs when agents meet at the same node. We consider the setting where n agents are dispersed (one per node) on an anonymous, arbitrary n-node, m-edge graph G. The goal is to construct tree structures such that each tree edge is recognized by at least one of its endpoint agents, minimizing both time and memory. We work in the synchronous model, measuring time in rounds, and assume agents have no prior knowledge of graph parameters such as n, m, D, Delta. A known solution constructs a BFS tree in 0 (D Delta) rounds with O(log n) memory per agent, assuming the root is known. We present a deterministic algorithm that constructs a BFS tree in O(min (D Delta, m log n) + n log n + Delta log(2) n) rounds with O(log n) bits per agent, without any prior root knowledge. In discovering the root, we solve leader election and MST. Our leader election and MST algorithms run in O(n log n + Delta log(2) n) rounds using O (log n) memory. Previous results require O(m) rounds and O(log(2) n) memory for leader election, and O(m + n log n) rounds and 0 (max(Delta, log n) log n) memory for MST. Our results improve over this prior work. We assume each agent knows A, the maximum identifier, bounded by a polynomial in n (i.e., lambda <= n(c) for some constant c >= 1).
Keywords:
Distributed Graph Algorithms
Leader Election
Minimum Spanning Tree
Breadth First Search Tree
Mobile Agents
Mobile Robots
Autonomous Agents
Journal
S
IF:
0
Papers:
34
Citations:
0