ISSN:
1573-7640
Keywords:
Parallel graph algorithms
;
concurrent logic programming
;
partitioning
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01408019
Permalink
