کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
6875774 | 1441985 | 2017 | 11 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Upgrading min-max spanning tree problem under various cost functions
ترجمه فارسی عنوان
به روز رسانی مین-حداکثر مشکل درخت تحت توابع هزینه های مختلف
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
مشکلات محل سکونت، ارتقاء مشکلات، حداکثر مفهوم درخت درختی،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
This paper addresses upgrading min-max spanning tree problem (MMST). Given a graph G(V,E), the aim of this problem is to modify edge weights under certain limits and given budget so that the MMST with respect to perturbed graph improves as much as possible. We present a complexity result for general non-decreasing cost functions. In special case, it is shown that the problem under linear and sum-type Hamming cost function can be solved in O(|E|2) and O(|E|logâ¡|E|logâ¡|V|) time, respectively.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 704, 15 December 2017, Pages 87-91
Journal: Theoretical Computer Science - Volume 704, 15 December 2017, Pages 87-91
نویسندگان
Ali Reza Sepasian, Ehsan Monabbati,