Please use this identifier to cite or link to this item:
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
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
RMID: 0020065609
DOI: 10.1023/A:1022080713267
Published version:
Appears in Collections: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.