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

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
نویسندگان
,