Title :
Distributed BFS algorithms
Author :
Awerbuch, Baruch ; Gallager, Robert G.
Abstract :
This paper develops a new distributed BFS algorithm for an asynchronous communication network. This paper presents two new BFS algorithms with improved communication complexity. The first algorithm has complexity O((E+V1.5)¿logV) in communication and O(V1.5¿logV) in time. The second algorithm uses the technique of the first recursively and achieves O(E¿2 √logVloglogV) in communication and O(V¿2√logVloglogV) in time.
Keywords :
Asynchronous communication; Bandwidth; Complexity theory; Distributed algorithms; Interactive systems; Internet; Particle separators; Propagation delay; Video recording; Web sites;
Conference_Titel :
Foundations of Computer Science, 1985., 26th Annual Symposium on
Conference_Location :
Portland, OR, USA
Print_ISBN :
0-8186-0644-4
DOI :
10.1109/SFCS.1985.20
