ISSN:
1573-7640
Schlagwort(e):
Parallel graph algorithms
;
concurrent logic programming
;
partitioning
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
Notizen:
Abstract A partitioned, priority-queue algorithm for solving the single-source best-path problem is defined and evaluated. Finding single-source paths for sparse graphs is notable because of its definitelack of parallelism-no known algorithms are scalable. Qualitatively, we discuss the close relationships between our algorithm and previous work by Quinn, Chikayama, and others. Performance measurements of variations of the algorithm, implemented both in concurrent and imperative programming languages on a shared-memory multiprocessor, are presented. This quantitative analysis of the algorithms provides insights into the tradeoffs between complexity and overhead in graph-searching executed in high-level parallel languages with automatic task scheduling.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF01408019
Permalink