Distributed BFS algorithms

1 October 1985

conference paper
Published by Institute of Electrical and Electronics Engineers (IEEE)

p. 250-256
https://doi.org/10.1109/sfcs.1985.20

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

This publication has 4 references indexed in Scilit:

A single source shortest path algorithm for a planar distributed network
Published by Springer Nature ,2005
An efficient network synchronization protocol
Published by Association for Computing Machinery (ACM) ,1984
A Distributed Algorithm for Minimum-Weight Spanning Trees
ACM Transactions on Programming Languages and Systems, 1983
Distributed Minimum Hop Algorithms
Published by Defense Technical Information Center (DTIC) ,1982