Experiments with the auction algorithm for the shortest path problem

Jesper Larsen, Ib Pedersen

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    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.
    Original languageEnglish
    JournalNordic Journal of Computing
    Volume6
    Issue number4
    Pages (from-to)403-421
    ISSN1236-6064
    Publication statusPublished - 1999

    Keywords

    • auction
    • performance results
    • shortest path
    • parallel computing

    Fingerprint Dive into the research topics of 'Experiments with the auction algorithm for the shortest path problem'. Together they form a unique fingerprint.

    Cite this