کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
478121 1446022 2014 11 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Fast and fine quickest path algorithm
ترجمه فارسی عنوان
سریعترین و سریعترین الگوریتم مسیر
کلمات کلیدی
یا در ارتباطات مخابراتی، سریعترین مسیر، مسیر غیر سلطه پشتیبانی شده
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی


• A novel quickest path algorithm is proposed.
• The algorithm runs in O(r(m+nlogn))O(r(m+nlogn)) time and uses O(m+n)O(m+n) space.
• It is a ratio-labeling algorithm working as a Dijkstra-like method.
• The method enumerates only supported efficient paths.
• Computational tests show that the algorithm performs very well.

We address the quickest path problem proposing a new algorithm based on the fact that its optimal solution corresponds to a supported non-dominated point in the objective space of the minsum–maxmin bicriteria path problem. This result allows us to design a label setting algorithm which improves all existing algorithms in the state-of-the-art, as it is shown in the extensive experiments carried out considering synthetic and real networks.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 238, Issue 2, 16 October 2014, Pages 596–606
نویسندگان
, ,