کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
488296 703864 2016 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Algorithms for the minimum spanning tree problem with resource allocation
ترجمه فارسی عنوان
الگوریتم برای مسئله درخت پوشا حداقل با تخصیص منابع
کلمات کلیدی
مسئله درخت پوشا حداقل؛ تخصیص منابع؛ تجزیه و تحلیل تجارت کردن؛ روش شاخه و حد
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
چکیده انگلیسی

We formulate the minimum spanning tree problem with resource allocation   (MSTRA) in two ways, as discrete and continuous optimization problems (d-MSTRA/c-MSTRA), prove these to be NPNP-hard, and present algorithms to solve these problems to optimality. We reformulate d-MSTRA as the knapsack constrained minimum spanning tree problem  , and solve this problem using a previously published branch-and-bound algorithm. By applying a ‘peg test’, the size of d-MSTRA is (significantly) reduced. To solve c-MSTRA, we introduce the concept of ff-fractionalfractionalsolutionsolution, and prove that an optimal solution can be found within this class of solutions. Based on this fact, as well as conditions for ‘pruning’ subproblems, we develop an enumerative algorithm to solve c-MSTRA to optimality. We implement these algorithms in ANSI C programming language and, through extensive numerical tests, evaluate the performance of the developed codes on various types of instances.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Operations Research Perspectives - Volume 3, 2016, Pages 5–13
نویسندگان
, ,