کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6874653 | 1441186 | 2018 | 30 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
An improved algorithm for the minmax regret path centdian problem on trees
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
This paper studies the problem of finding a path centdian on a tree in which vertex weights are uncertain and the uncertainty is characterized by given intervals. It is required to find a minmax regret solution, which minimizes the worst-case loss in the objective function. Puerto et al. had an O(n5logâ¡n)-time algorithm for this problem. In this paper, we first show that there is a special case which their algorithm does not handle and it is easy to modify their algorithm to cope with this exception. Then, we further present an improved O(n4)-time algorithm.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 97, November 2018, Pages 94-105
Journal: Journal of Computer and System Sciences - Volume 97, November 2018, Pages 94-105
نویسندگان
Jhih-Hong Ye, Chih-Yu Li, Biing-Feng Wang,