Title :
Notes on `divide-and-conquer-based optimal parallel algorithms for some graph problems on EREW PRAM model´
Author :
Das, Sajal K. ; Deo, Narsingh
Author_Institution :
Dept. of Comput. Sci., North Texas Univ., Denton, TX, USA
fDate :
7/1/1990 12:00:00 AM
Abstract :
A proof of correctness is presented for the connected-components algorithm. In addition, the authors present a modified implementation of the PARALLELFCS algorithm, which finds a fundamental cycle set of a connected graph. Analyzing the processor-(time)2 complexity, it is shown that the modified version has a better performance because it is optimally scalable to a larger number of processors
Keywords :
computational complexity; graph theory; parallel algorithms; program verification; EREW PRAM model; PARALLELFCS; complexity; connected graph; connected-components algorithm; divide-and-conquer algorithm; exclusive read exclusive write; fundamental cycle set; graph problems; optimal parallel algorithms; parallel random access machine; proof of correctness; Algorithm design and analysis; Calibration; Capacitors; Hardware; Parallel algorithms; Phase change random access memory; Quantization; Read only memory; Switching circuits; Voltage;
Journal_Title :
Circuits and Systems, IEEE Transactions on
