کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
480660 | 1446128 | 2010 | 9 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Solving the 2-rooted mini-max spanning forest problem by branch-and-bound
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
The 2-rooted mini-max spanning forest problem is to find a spanning forest with two given root nodes on an undirected graph, such that the maximum tree cost in this forest is minimized. We introduce a branch-and-bound algorithm based on selecting nodes. On test instances up to 50 nodes the algorithm gives much better computational results than a known algorithm that is based on selecting edges. Furthermore the new algorithm can easily solve problem instances up to 80 nodes.We consider some alternative and polynomial criteria. Finally we discuss some generalizations, e.g., the problem without given root nodes, i.e., the root nodes have to be chosen.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 203, Issue 1, 16 May 2010, Pages 50–58
Journal: European Journal of Operational Research - Volume 203, Issue 1, 16 May 2010, Pages 50–58
نویسندگان
M. Mekking, A. Volgenant,