Reducing complexities of the distributed max‐flow and breadth‐first‐search algorithms by means of network synchronization
Baruch Awerbuch · Networks · 1985
Abstract This article presents new simple distributed Maximum Flow and Breadth‐First Search algorithms for an asynchronous communication network. Our algorithms improve the best known algorithms both in the communication and time complexities. The basic idea is first to “synchronize” the network and then to apply synchronous algorithms which use efficiently the parallelism of the model.