Physical Sciences and Mathematics Commons^™

Constructing Bfs Trees Using Tokens To Balance Speed And Network Traffic, Michael Spencer

UNLV Theses, Dissertations, Professional Papers, and Capstones

Constructing BFS trees rooted at each node of a network helps solve many problems. Reliable communication to other nodes is easily managed and metrics such as the network diameter, shortest path between any two nodes, the center, the radius, and others can be easily computed. A traditional way to form a BFS tree from each node is for all nodes to construct their trees in parallel. While this is the fastest way to accomplish this task, it also requires a large amount of network traffic. In this thesis, we present a way to use a token passing algorithm to form …