کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
13433425 | 1842819 | 2020 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Shortest paths with ordinal weights
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: Shortest paths with ordinal weights Shortest paths with ordinal weights](/preview/png/13433425.png)
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 280, Issue 3, 1 February 2020, Pages 1160-1170
Journal: European Journal of Operational Research - Volume 280, Issue 3, 1 February 2020, Pages 1160-1170
نویسندگان
Luca E. Schäfer, Tobias Dietz, Nicolas Fröhlich, Stefan Ruzika, José R. Figueira,