Auction algorithms for shortest hyperpath problems

The auction-reduction algorithm is a strongly polynomial version of the auc tion method for the shortest path problem. In this paper we extend the auct ion-reduction algorithm to different types of shortest hyperpath problems i n directed hypergraphs. The results of preliminary computational experience s show that the auction-reduction method is comparable to other known metho ds for specific classes of hypergraphs.