کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
394317 | 665791 | 2012 | 15 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
New heuristics for two bounded-degree spanning tree problems
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
هوش مصنوعی
پیش نمایش صفحه اول مقاله
چکیده انگلیسی
A vertex v of a connected graph G = (V, E) is called a branch vertex if its degree is greater than two. Pertaining to branch vertices, this paper studies two optimization problems having roots in the domain of optical networks. The first one, referred to as MBV, seeks a spanning tree T of G with the minimum number of branch vertices, whereas the second problem, referred to as MDS, seeks a spanning tree T of G with the minimum degree sum of branch vertices. Both MBV and MDS are NP-Hard. Two heuristics approaches are presented for each problem. The first approach is a problem specific heuristic, whereas the latter one is a hybrid ant-colony optimization algorithm. Computational results show the effectiveness of our proposed approaches.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Information Sciences - Volume 195, 15 July 2012, Pages 226-240
Journal: Information Sciences - Volume 195, 15 July 2012, Pages 226-240
نویسندگان
Shyam Sundar, Alok Singh, André Rossi,