کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435606 | 689919 | 2015 | 10 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Two paths location of a tree with positive or negative weights
ترجمه فارسی عنوان
دو مسیر محل یک درخت با وزن مثبت یا منفی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
سلام، مسیر، درخت، نیمه ناپسند
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
• This paper studies two problems of locating two paths in weighted trees.
• We provide an algorithm in time O(n2)O(n2) by the optimal properties for the one problem.
• We provide an algorithm in time O(n3)O(n3) for the other problem.
This paper studies two problems of locating two paths in a tree with positive and negative weights. The first problem has objective to minimize the sum of minimum weighted distances from every vertex of the tree to the two paths, while the second is to minimize the sum of the weighted minimum distances from every vertex of the tree to the two paths. We develop an O(n2)O(n2) algorithm based on the optimal properties for the first problem, and also an O(n3)O(n3) algorithm for the second problem.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 607, Part 3, 23 November 2015, Pages 296–305
Journal: Theoretical Computer Science - Volume 607, Part 3, 23 November 2015, Pages 296–305
نویسندگان
Jianjie Zhou, Liying Kang, Erfang Shan,