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