Bottleneck shortest paths on a partially ordered scale

In bottleneck combinatorial problems, admissible solutions are compared with respect to their maximal elements. In such problems, one may work with an ordinal evaluation scale instead of a numerical scale. We consider here a generalization of this problem in which one only has a partially ordered scale (instead of a completely ordered scale). After the introduction of a mappimax comparison operator between sets of evaluations (which boils down to the classical operator when the order is complete), we establish computational complexity results for this variation of the shortest path problem. Finally, we formulate our problem as an algebraic shortest path problem and suggest adequate algorithms to solve it in the subsequent semiring.Received: June 2002, Revised: March 2003, AMS classification: 05C50, 16Y60, 90B06Olivier Spanjaard: Corresponding author.