Nordic Journal of Computing Bibliography

Jesper Larsen and Ib Pedersen. Experiments with the Auction Algorithm for the Shortest Path Problem. Nordic Journal of Computing, 6(4):403-421, Winter 1999.

The 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.

Categories and Subject Descriptors: G.2.2 [Discrete Mathematics]: Graph Theory; G.4 [Mathematical Software]

Additional Key Words and Phrases: shortest path, auction, parallel computing, performance results


  • Nordic Journal of Computing homepage
  • Bibliography top level
  • Nordic Journal of Computing Author Index
  • Search the HBP database