Experiments with the auction algorithm for the shortest path problem

Jesper Larsen, Ib Pedersen

AbstractThe auction approach for the shortest path problem (SPP) as introduced by Bertsekas is tested experimentally. Parallel algorithms using the auction approach are developed and tested. Both the sequential and parallel auction algorithms perform significantly worse than a state-of-the-art Dijkstra-like reference algorithm. Experiments are run on a distributed-memory MIMD class Meiko parallel computer.
Keywordsshortest path, auction, parallel computing, performance results
TypeJournal paper [With referee]
JournalNordic Journal of Computing
Year1999    Vol. 6    pp. 403-421
PublisherPublishing Association Nordic Journal of Computing
BibTeX data [bibtex]
IMM Group(s)Operations Research

Back  ::  IMM Publications