کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4959080 | 1445467 | 2017 | 22 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A branch-and-cut algorithm for the minimum branch vertices spanning tree problem
ترجمه فارسی عنوان
الگوریتم شاخه ای و برش برای حداقل رشته های شاخه درخت
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
درخت پوشا، ریشه شاخه، شعبه و برش،
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
علوم کامپیوتر (عمومی)
چکیده انگلیسی
Given a connected undirected graph G=(V,E), the Minimum Branch Vertices Problem (MBVP) asks for a spanning tree of G with the minimum number of vertices having degree greater than two in the tree. These are called branch vertices. This problem, with applications in the context of optical networks, is known to be NP-hard. We model the MBVP as an integer linear program, with undirected variables, we derive valid inequalities and we prove that some of these are facet defining. We then develop a hybrid formulation containing undirected and directed variables. Both models are solved with branch-and-cut. Comparative computational results show the superiority of the hybrid formulation.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Computers & Operations Research - Volume 81, May 2017, Pages 322-332
Journal: Computers & Operations Research - Volume 81, May 2017, Pages 322-332
نویسندگان
Selene Silvestri, Gilbert Laporte, Raffaele Cerulli,