کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
5775581 | 1631740 | 2018 | 7 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Primal dual based algorithm for degree-balanced spanning tree problem
ترجمه فارسی عنوان
الگوریتم اولیه مبتنی بر دوگانه برای مشکل درخت درخت درختی
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
درخت نفوذی درجه تابع هدف غیرخطی الگوریتم اولیه دوگانه،
موضوعات مرتبط
مهندسی و علوم پایه
ریاضیات
ریاضیات کاربردی
چکیده انگلیسی
This paper studies approximation algorithm for the degree-balanced spanning tree (DBST) problem. Given a graph G=(V,E), the goal is to find a spanning tree T such that âvâ¯ââ¯VdegT(v)2 is minimized, where degT(v) denotes the degree of node v in tree T. The idea of taking squares on node degrees is to manifest the role of nodes with large degree, and thus minimizing the sum will result in a comparatively balanced degree distribution. This is a non-linear objective function. We prove that DBST is NP-hard, and then develop a primal-dual based algorithm with a guaranteed performance ratio.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Applied Mathematics and Computation - Volume 316, 1 January 2018, Pages 167-173
Journal: Applied Mathematics and Computation - Volume 316, 1 January 2018, Pages 167-173
نویسندگان
Yingli Ran, Zhihao Chen, Shaojie Tang, Zhao Zhang,