Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
13433425 | European Journal of Operational Research | 2020 | 11 Pages |
Abstract
We investigate the single-source-single-destination “shortest” path problem in directed, acyclic graphs with ordinal weighted arc costs. We define the concepts of ordinal dominance and efficiency for paths and their associated ordinal levels, respectively. Further, we show that the number of ordinally non-dominated path vectors from the source node to every other node in the graph is polynomially bounded and we propose a polynomial time labeling algorithm for solving the problem of finding the set of ordinally non-dominated path vectors from source to sink.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Luca E. Schäfer, Tobias Dietz, Nicolas Fröhlich, Stefan Ruzika, José R. Figueira,