کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419946 | 683877 | 2013 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Online binary minimax trees
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
In the binary minimax tree problem we are given non-negative weights W=(w1,…,wn)W=(w1,…,wn). The task is to find a rooted binary tree TT with nn leaves and an assignment of the leaves to the weights such that the maximum over all leaves ll of the weight of ll plus the depth of ll is minimized.We present an online algorithm for building an optimal binary minimax tree with integral weights that runs in O(nlogn/loglogn) time using exponential search trees. Moreover, we show that no online algorithm computing an optimal minimax tree exists if we allow non-integral real weights.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 161, Issues 16–17, November 2013, Pages 2556–2562
Journal: Discrete Applied Mathematics - Volume 161, Issues 16–17, November 2013, Pages 2556–2562
نویسندگان
Jens Maßberg,