Dokumentenserver der Freien Universität Berlin

Objekt-Metadaten

An efficient parallel algorithm for the all pairs shortest path problem using processor arrays with reconfigurable bus systems
Wankar, Rajeev ;  Fehr, Elfriede ;  Chaudhari, N. S. ;  Universität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik

Main titleAn efficient parallel algorithm for the all pairs shortest path problem using processor arrays with reconfigurable bus systems
AuthorWankar, Rajeev
AuthorFehr, Elfriede
AuthorChaudhari, N. S.
InstitutionUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
No. of Pages17 S.
Series Freie Universität Berlin, Fachbereich Mathematik und Informatik : Ser. B, Informatik ; 99,13
KeywordsSplitting, SPP, PARBS
Classification (DDC)004 Data processing and Computer science
AbstractThe all pairs shortest path problem is a class of the algebraic path problem. Many parallel algorithms for the solution
of this problem appear in the literature. One of the efficient parallel algorithms on W-RAM model is given by Kucera[
17]. Though efficient, algorithms written for the W-RAM model of parallel computation are too idealistic to be
implemented on the current hardware. In this report we present an efficient parallel algorithm for the solution of this
problem using a relatively new model of parallel computing, Processor Arrays with Reconfigurable Bus Systems. The
parallel time complexity of this algorithm is O(log2 n) and processors complexity is n2 × n × n.
Documents
PDF-Datei
If your browser can't open the file, please download the file first and then open it
 
FU DepartmentDepartment of Mathematics and Computer Science
Other affiliation(s)Institut für Informatik
Year of publication1999
Type of documentMaps
LanguageEnglish
Terms of use/Rights Nutzungsbedingungen
Created at2009-04-15 : 10:20:32
Last changed2014-01-23 : 04:21:23
 
Static URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000001610
Statistics