Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 1 of 1
Full-Text Articles in Physical Sciences and Mathematics
Constructing Bfs Trees Using Tokens To Balance Speed And Network Traffic, Michael Spencer
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 …