Parallel graph algorithms based upon broadcast communications
- 1 January 1990
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. 39 (12) , 1468-1472
- https://doi.org/10.1109/12.61071
Abstract
[[abstract]]Some common guidelines that can be used to design parallel algorithms under the single-channel broadcast communication model are presented. Several graph problems are solved, including topological ordering, the connected component problem, breadth-first search, and depth-first search. If an ideal conflict resolution scheme is used, all of the algorithms require O(n) time by using n processors. Under such a situation, the algorithms are all optimal. If a realistic conflict resolution is used, the algorithms require O(n log n) time by using n/log n processors. For both cases, all of the algorithms achieve optimal speedups.[[fileno]]2030256010094[[department]]資訊工程學Keywords
This publication has 9 references indexed in Scilit:
- Distributed sorting on local area networksIEEE Transactions on Computers, 1988
- Parallel algorithms for analyzing activity networksBIT Numerical Mathematics, 1986
- Broadcast Communications and Distributed AlgorithmsIEEE Transactions on Computers, 1986
- Parallel graph algorithmsACM Computing Surveys, 1984
- Parallel computation and conflicts in memory accessInformation Processing Letters, 1982
- Finding an extremum in a networkACM SIGARCH Computer Architecture News, 1982
- Parallel Matrix and Graph AlgorithmsSIAM Journal on Computing, 1981
- Tree algorithms for packet broadcast channelsIEEE Transactions on Information Theory, 1979
- Depth-First Search and Linear Graph AlgorithmsSIAM Journal on Computing, 1972