Please use this identifier to cite or link to this item: http://hdl.handle.net/2440/36754
Citations
Scopus Web of ScienceĀ® Altmetric
?
?
Full metadata record
DC FieldValueLanguage
dc.contributor.authorLi, J.en
dc.contributor.authorPan, Y.en
dc.contributor.authorShen, H.en
dc.date.issued2003en
dc.identifier.citationJournal of Supercomputing, 2003; 24(3):251-258en
dc.identifier.issn0920-8542en
dc.identifier.urihttp://hdl.handle.net/2440/36754-
dc.descriptionThe original publication is available at www.springerlink.comen
dc.description.abstractTopological 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.en
dc.description.statementofresponsibilityJie Li, Yi Pan and Hong Shenen
dc.language.isoenen
dc.publisherKluwer Academic Publen
dc.source.urihttp://www.springerlink.com/content/h406q68ggnv70g24/en
dc.subjectanalysis of algorithms; graph problem; massive parallelism; optical bus; time complexityen
dc.titleMore efficient topological sort using reconfigurable optical busesen
dc.typeJournal articleen
dc.identifier.rmid0020065609en
dc.identifier.doi10.1023/A:1022080713267en
dc.identifier.pubid49657-
pubs.library.collectionComputer Science publicationsen
pubs.verification-statusVerifieden
pubs.publication-statusPublisheden
dc.identifier.orcidShen, H. [0000-0002-3663-6591]en
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.