Please use this identifier to cite or link to this item:
https://hdl.handle.net/2440/36754
Citations | ||
Scopus | Web of ScienceĀ® | Altmetric |
---|---|---|
?
|
?
|
Type: | Journal article |
Title: | More efficient topological sort using reconfigurable optical buses |
Author: | Li, J. Pan, Y. Shen, H. |
Citation: | Journal of Supercomputing, 2003; 24(3):251-258 |
Publisher: | Kluwer Academic Publ |
Issue Date: | 2003 |
ISSN: | 0920-8542 |
Statement of Responsibility: | Jie Li, Yi Pan and Hong Shen |
Abstract: | Topological sort of an acyclic graph has many applications such as job scheduling and network analysis. Due to its importance, it has been tackled on many models. Dekel et al. [3], proposed an algorithm for solving the problem in O(log2 N) time on the hypercube or shuffle-exchange networks with O(N 3) processors. Chaudhuri [2], gave an O(log N) algorithm using O(N 3) processors on a CRCW PRAM model. On the LARPBS (Linear Arrays with a Reconfigurable Pipelined Bus System) model, Li et al. [5] showed that the problem for a weighted directed graph with N vertices can be solved in O(log N) time by using N 3 processors. In this paper, a more efficient topological sort algorithm is proposed on the same LARPBS model. We show that the problem can be solved in O(log N) time by using N 3/log N processors. We show that the algorithm has better time and processor complexities than the best algorithm on the hypercube, and has the same time complexity but better processor complexity than the best algorithm on the CRCW PRAM model. |
Keywords: | analysis of algorithms graph problem massive parallelism optical bus time complexity |
Description: | The original publication is available at www.springerlink.com |
DOI: | 10.1023/A:1022080713267 |
Published version: | http://www.springerlink.com/content/h406q68ggnv70g24/ |
Appears in Collections: | Aurora harvest Computer Science publications |
Files in This Item:
There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.