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 |
Haupttitel | An efficient parallel algorithm for the all pairs shortest path problem using processor arrays with reconfigurable bus systems |
Autor | Wankar, Rajeev |
Autor | Fehr, Elfriede |
Autor | Chaudhari, N. S. |
Institution/Körperschaft | Universität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik |
Seitenzahl | 17 S. |
Schriftenreihe | Freie Universität Berlin, Fachbereich Mathematik und Informatik : Ser. B, Informatik ; 99,13 |
Freie Schlagwörter | Splitting, SPP, PARBS |
DDC | 004 Datenverarbeitung; Informatik |
Zusammenfassung | The 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. |
Dokumente |
PDF-Datei
Falls Ihr Browser eine Datei nicht öffnen kann, die Datei zuerst herunterladen und dann öffnen.
|
Fachbereich/Einrichtung | FB Mathematik und Informatik |
Arbeitsbereich/Institut | Institut für Informatik |
Erscheinungsjahr | 1999 |
Dokumententyp/-Sammlungen | Arbeitspapier |
Sprache | Englisch |
Rechte | Nutzungsbedingungen |
Erstellt am | 15.04.2009 - 10:20:32 |
Letzte Änderung | 27.02.2015 - 08:24:57 |
Statische URL | http://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000001610 |
Zugriffsstatistik | |