Parallel shortest path auction algorithms

L. C. Polymenakos, D. P. Bertsekas

Research output: Contribution to journalArticlepeer-review

11 Scopus citations


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 languageEnglish (US)
Pages (from-to)1221-1247
Number of pages27
JournalParallel Computing
Issue number9
StatePublished - Sep 1994
Externally publishedYes


  • 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


Dive into the research topics of 'Parallel shortest path auction algorithms'. Together they form a unique fingerprint.

Cite this