کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420416 683934 2009 6 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A note on the minimum bounded edge-partition of a tree
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
A note on the minimum bounded edge-partition of a tree
چکیده انگلیسی

Minimum bounded edge-partition divides the edge set of a tree into the minimum number of disjoint connected components given a maximum weight for any component. It is an adaptation of the uniform edge-partition of a tree. An optimization algorithm is developed for this NP-hard problem, based on repeated bin packing of inter-related instances. The algorithm has linear running time for the class of ‘balanced trees’ common for the stochastic programming application which motivated investigation of this problem.Fast 2-approximation algorithms are formed for general instances by replacing the optimal bin packing with almost any bin packing heuristic. The asymptotic worst-case ratio of these approximation algorithms is never better than the absolute worst-case ratio of the bin packing heuristic used.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 13, 6 July 2009, Pages 2958–2963
نویسندگان
,