Bottleneck shortest paths on a partially ordered scale
Spanjaard, Olivier; Monnot, Jérôme (2003), Bottleneck shortest paths on a partially ordered scale, 4OR, 1, 3, p. 225-241. http://dx.doi.org/10.1007/s10288-003-0017-3
TypeArticle accepté pour publication ou publié
External document linkhttp://hal.archives-ouvertes.fr/hal-00004060/en/
MetadataShow full item record
Abstract (EN)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 $\max$ 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.
Subjects / KeywordsShortest path; partial order; algebraic methods; bottleneck problems
Showing items related by title and author.
Gourvès, Laurent; Escoffier, Bruno; Spanjaard, Olivier; Monnot, Jérôme (2010) Article accepté pour publication ou publié