dc.contributor.author
Wankar, Rajeev
dc.contributor.author
Fehr, Elfriede
dc.contributor.author
Chaudhari, N. S.
dc.date.accessioned
2018-06-08T07:31:16Z
dc.date.available
2009-04-15T10:20:32.848Z
dc.identifier.uri
https://refubium.fu-berlin.de/handle/fub188/18138
dc.identifier.uri
http://dx.doi.org/10.17169/refubium-21848
dc.description.abstract
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.
en
dc.relation.ispartofseries
urn:nbn:de:kobv:188-fudocsseries000000000021-2
dc.rights.uri
http://www.fu-berlin.de/sites/refubium/rechtliches/Nutzungsbedingungen
dc.subject.ddc
000 Informatik, Informationswissenschaft, allgemeine Werke::000 Informatik, Wissen, Systeme::004 Datenverarbeitung; Informatik
dc.title
An efficient parallel algorithm for the all pairs shortest path problem using
processor arrays with reconfigurable bus systems
refubium.affiliation
Mathematik und Informatik
de
refubium.affiliation.other
Institut für Informatik
refubium.mycore.fudocsId
FUDOCS_document_000000001610
refubium.resourceType.isindependentpub
no
refubium.series.name
Freie Universität Berlin, Fachbereich Mathematik und Informatik
refubium.series.reportNumber
99-13
refubium.mycore.derivateId
FUDOCS_derivate_000000000348
dcterms.accessRights.openaire
open access
