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