Premium
Reducing complexities of the distributed max‐flow and breadth‐first‐search algorithms by means of network synchronization
Author(s) -
Awerbuch Baruch
Publication year - 1985
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230150404
Subject(s) - asynchronous communication , computer science , synchronization (alternating current) , maximum flow problem , algorithm , simple (philosophy) , parallelism (grammar) , flow network , distributed algorithm , depth first search , breadth first search , parallel algorithm , flow (mathematics) , telecommunications network , parallel computing , distributed computing , search algorithm , mathematics , mathematical optimization , computer network , channel (broadcasting) , philosophy , epistemology , geometry
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.