Abstract
In this paper we discuss the parallel implementation of the auction algorithm for shortest path problems. We show that both the one-sided and the two-sided versions of the algorithm admit asynchronous implementations. We implemented the parallel schemes for the algorithm on a shared memory machine and tested its efficiency under various degrees of synchronization and for different types of problems. We discuss the efficiency of the parallel implementation of the many origins-one destination problem, the all origins-one destination problem, and the many origins-many destinations problem.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 1221-1247 |
| Number of pages | 27 |
| Journal | Parallel Computing |
| Volume | 20 |
| Issue number | 9 |
| DOIs | |
| State | Published - Sep 1994 |
| Externally published | Yes |
Keywords
- Auction algorithm
- Parallel implementation
- Performance results
- Shared memory multiprocessor
- Shortest path problem
ASJC Scopus subject areas
- Software
- Theoretical Computer Science
- Hardware and Architecture
- Computer Networks and Communications
- Computer Graphics and Computer-Aided Design
- Artificial Intelligence